Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- class Solution {
- /**
- * Returns true iff team x can still win the Cup.
- */
- public static boolean solve(InputStream in) {
- List<Node> nodes = new ArrayList<Node>();
- List<Team> teams = new ArrayList<Team>();
- Scanner sc = new Scanner(in);
- int m = sc.nextInt();
- // parse all lines into graph
- for (int i=0; i<m;i++) {
- Team t = new Team(sc.nextInt(),sc.nextInt(),sc.nextInt());
- for (int j = 0; j < t.g; j++) {
- t.opp[j] = sc.nextInt();
- }
- teams.add(t);
- }
- Node src = new Node(0);
- Node sink = new Node(-1);
- nodes.add(src);
- nodes.add(sink);
- sc.close();
- Team x = teams.get(0);
- int xWins = x.w + x.g;
- System.out.println(x.w);
- System.out.println(x.g);
- System.out.println(x.id);
- // Create all nodes for teams except first
- for(int i=1; i<m; i++) {
- Node teamNode = new Node(i);
- teamNode.addEdge(sink, xWins - teams.get(i).w);
- nodes.add(teamNode);
- }
- int nc = m+1;
- // loop through teams and create nodes for matches
- for(int i=1; i<m; i++) {
- Node teamNode = nodes.get(i);
- Team t = teams.get(i);
- for(int j=1; j<t.g; j++) {
- if (xWins - teams.get(t.opp[j]-1).w <= 0) {
- return false;
- }
- Node matchNode = new Node(nc++);
- nodes.add(matchNode);
- // add edge from the source to the match
- src.addEdge(matchNode, 1);
- // attach edges to the teamNodes of this match
- Node o = nodes.get(t.opp[j]-1);
- matchNode.addEdge(o, Integer.MAX_VALUE);
- matchNode.addEdge(teamNode, Integer.MAX_VALUE);
- }
- }
- Graph g = new Graph(nodes, src, sink);
- g.maximizeFlow();
- for (Edge e : src.getEdges()) {
- System.out.println(e.getCapacity());
- System.out.println(e.getFlow());
- if (e.getCapacity() > e.getFlow()) {
- return false;
- }
- }
- return true;
- }
- }
- class Team {
- Team(int id, int w, int g) {
- this.id = id;
- this.w = w;
- this.g = g;
- opp = new int[g];
- }
- int id;
- int w;
- int g;
- int opp[];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement