Advertisement
Guest User

Untitled

a guest
Apr 18th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.24 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Solution {
  5.  
  6.   /**
  7.    * Returns true iff team x can still win the Cup.
  8.    */
  9.   public static boolean solve(InputStream in) {
  10.     List<Node> nodes = new ArrayList<Node>();
  11.     List<Team> teams = new ArrayList<Team>();
  12.  
  13.     Scanner sc = new Scanner(in);
  14.    
  15.     int m = sc.nextInt();
  16.    
  17.     // parse all lines into graph
  18.     for (int i=0; i<m;i++) {
  19.       Team t = new Team(sc.nextInt(),sc.nextInt(),sc.nextInt());
  20.      
  21.       for (int j = 0; j < t.g; j++) {
  22.         t.opp[j] = sc.nextInt();
  23.       }
  24.       teams.add(t);
  25.     }
  26.    
  27.     Node src = new Node(0);
  28.     Node sink = new Node(-1);
  29.     nodes.add(src);
  30.     nodes.add(sink);
  31.     sc.close();
  32.    
  33.     Team x = teams.get(0);
  34.     int xWins = x.w + x.g;
  35.       System.out.println(x.w);
  36.       System.out.println(x.g);
  37.       System.out.println(x.id);
  38.    
  39.     // Create all nodes for teams except first
  40.     for(int i=1; i<m; i++) {
  41.       Node teamNode = new Node(i);
  42.       teamNode.addEdge(sink, xWins - teams.get(i).w);
  43.       nodes.add(teamNode);
  44.     }
  45.    
  46.     int nc = m+1;
  47.    
  48.     // loop through teams and create nodes for matches
  49.     for(int i=1; i<m; i++) {
  50.       Node teamNode = nodes.get(i);
  51.       Team t = teams.get(i);
  52.       for(int j=1; j<t.g; j++) {
  53.         if (xWins - teams.get(t.opp[j]-1).w <= 0) {
  54.           return false;
  55.         }
  56.        
  57.         Node matchNode = new Node(nc++);
  58.         nodes.add(matchNode);
  59.         // add edge from the source to the match
  60.         src.addEdge(matchNode, 1);
  61.         // attach edges to the teamNodes of this match
  62.         Node o = nodes.get(t.opp[j]-1);
  63.         matchNode.addEdge(o, Integer.MAX_VALUE);
  64.         matchNode.addEdge(teamNode, Integer.MAX_VALUE);
  65.       }
  66.     }
  67.    
  68.    
  69.     Graph g = new Graph(nodes, src, sink);
  70.     g.maximizeFlow();
  71.    
  72.     for (Edge e : src.getEdges()) {
  73.       System.out.println(e.getCapacity());
  74.       System.out.println(e.getFlow());
  75.       if (e.getCapacity() > e.getFlow()) {
  76.         return false;
  77.       }
  78.     }
  79.    
  80.     return true;
  81.   }
  82. }
  83.  
  84.  
  85. class Team {
  86.   Team(int id, int w, int g) {
  87.     this.id = id;
  88.     this.w = w;
  89.     this.g = g;
  90.     opp = new int[g];
  91.   }
  92.  
  93.   int id;
  94.   int w;
  95.   int g;
  96.   int opp[];
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement