• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 18th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.       }
25.     }
26.
27.     Node src = new Node(0);
28.     Node sink = new Node(-1);
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);
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++);
59.         // add edge from the source to the match
61.         // attach edges to the teamNodes of this match
62.         Node o = nodes.get(t.opp[j]-1);
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top