import edu.princeton.cs.algs4.FlowEdge;

 import edu.princeton.cs.algs4.FlowNetwork;

 import edu.princeton.cs.algs4.FordFulkerson;

 import edu.princeton.cs.algs4.ST;

 import edu.princeton.cs.algs4.Queue;

 import edu.princeton.cs.algs4.In;

 import edu.princeton.cs.algs4.StdOut;

 public class BaseballElimination

 {

     private int numberOfTeams;

     private ST<String, Integer> st;

     private int[] wins;

     private int[] losses;

     private int[] remaining;

     private int[][] against;

     private String[] teamName;

     public BaseballElimination(String filename)

     {

         st = new ST<String, Integer>();

         In in = new In(filename);

         numberOfTeams = in.readInt();

         wins = new int[numberOfTeams];

         losses = new int[numberOfTeams];

         remaining = new int[numberOfTeams];

         teamName = new String[numberOfTeams];

         against = new int[numberOfTeams][numberOfTeams];

         for (int i = 0; i < numberOfTeams; i++)

         {

             String name = in.readString();

             st.put(name, i);

             wins[i] = in.readInt();

             losses[i] = in.readInt();

             remaining[i] = in.readInt();

             teamName[i] = name;

             for (int j = 0; j < numberOfTeams; j++)

                 against[i][j] = in.readInt();

         }

     }

     public int numberOfTeams()

     {

         return numberOfTeams;

     }

     public Iterable<String> teams()

     {

         return st.keys();

     }

     public int wins(String team)

     {

         if (!st.contains(team)) throw new IllegalArgumentException();

         int index = st.get(team);

         return wins[index];

     }

     public int losses(String team)

     {

         if (!st.contains(team)) throw new IllegalArgumentException();

         int index = st.get(team);

         return losses[index];

     }

     public int remaining(String team)

     {

         if (!st.contains(team)) throw new IllegalArgumentException();

         int index = st.get(team);

         return remaining[index];

     }

     public int against(String team1, String team2)

     {

         if (!st.contains(team1) || !st.contains(team2)) throw new IllegalArgumentException();

         int index1 = st.get(team1);

         int index2 = st.get(team2);

         return against[index1][index2];

     }

     private FlowNetwork createNetwork(String team)

     {

         int index = st.get(team);

         int num = numberOfTeams - 1;

         int V = num + 2 + num * (num - 1) / 2;

         int s = V - 2, t = V - 1;

         FlowNetwork net = new FlowNetwork(V);

         for (int i = 0; i < num; i++)

         {

             if (i < index)

             {

                 double capacity = wins[index] + remaining[index] - wins[i];

                 FlowEdge edge = new FlowEdge(i, t, capacity);

                 net.addEdge(edge);

             }

             else

             {

                 double capacity = wins[index] + remaining[index] - wins[i + 1];

                 FlowEdge edge = new FlowEdge(i, t, capacity);

                 net.addEdge(edge);

             }

         }

         int temp = num;

         for (int i = 0; i < num - 1; i++)

         {

             for (int j = i + 1; j < num; j++)

             {

                 FlowEdge edge = new FlowEdge(temp, j, Double.POSITIVE_INFINITY);

                 net.addEdge(edge);

                 edge = new FlowEdge(temp, i, Double.POSITIVE_INFINITY);

                 net.addEdge(edge);

                 int a = i, b = j;

                 if (i >= index) a++;

                 if (j >= index) b++;

                 double capacity = against[a][b];

                 edge = new FlowEdge(s, temp, capacity);

                 net.addEdge(edge);

                 temp++;

             }

         }

         return net;

     }

     public boolean isEliminated(String team)

     {

         if (!st.contains(team)) throw new IllegalArgumentException();

         int index = st.get(team);

         int num = numberOfTeams - 1;

         int V = num + 2 + num * (num - 1) / 2;

         int s = V - 2, t = V - 1;

         for (int i = 0; i < num; i++)

         {

             int j = i;

             if (j >= index) j++;

             if (wins[index] + remaining[index] < wins[j])

                 return true;

         }

         FlowNetwork net = createNetwork(team);

         FordFulkerson ff = new FordFulkerson(net, s, t);

         for (FlowEdge e : net.adj(s))

             if (e.capacity() != e.flow())

                 return true;

         return false;

     }

     public Iterable<String> certificateOfElimination(String team)

     {

         if (!st.contains(team)) throw new IllegalArgumentException();

         int index = st.get(team);

         int num = numberOfTeams - 1;

         int V = num + 2 + num * (num - 1) / 2;

         int s = V - 2, t = V - 1;

         Queue<String> certificate = new Queue<String>();

         boolean isEliminated = false;

         for (int i = 0; i < num; i++)

         {

             int j = i;

             if (j >= index) j++;

             if (wins[index] + remaining[index] < wins[j])

             {

                 isEliminated = true;

                 certificate.enqueue(teamName[j]);

             }

         }

         if (isEliminated) return certificate;

         FlowNetwork net = createNetwork(team);

         FordFulkerson ff = new FordFulkerson(net, s, t);

         for (int i = 0; i < num; i++)

         {

             if (ff.inCut(i))

             {

                 int j = i;

                 if (j >= index) j++;

                 certificate.enqueue(teamName[j]);

                 isEliminated = true;

             }

         }

         if (isEliminated) return certificate;

         return null;

     }

     public static void main(String[] args) {

         BaseballElimination division = new BaseballElimination(args[0]);

         for (String team : division.teams()) {

             if (division.isEliminated(team)) {

                 StdOut.print(team + " is eliminated by the subset R = { ");

                 for (String t : division.certificateOfElimination(team)) {

                     StdOut.print(t + " ");

                 }

                 StdOut.println("}");

             }

             else {

                 StdOut.println(team + " is not eliminated");

             }

         }

     }

 }