### Question:
MaxWeightClosure { public static int solve(List<Vertex> vertices, Set<Vertex> ans) { int n = vertices.size(); FlowNetwork flowNetwork = new FlowNetwork(n + 2); int total = 0; for (Vertex v : vertices) { if (v.weight() > 0) { total += v.weight(); flowNetwork.addEdge(new FlowEdge(n, v.idx(), v.weight())); } else { flowNetwork.addEdge(new FlowEdge(v.idx(), n + 1, -v.weight())); } for (Vertex nei : v.adj()) { flowNetwork.addEdge(new FlowEdge(v.idx(), nei.idx(), Double.POSITIVE_INFINITY)); } } FordFulkerson fordFulkerson = new FordFulkerson(flowNetwork, n, n + 1); for (Vertex v : vertices) { if (fordFulkerson.inCut(v.idx())) { ans.add(v); } } return total - (int) fordFulkerson.value(); }  static int solve(List<Vertex> vertices, Set<Vertex> ans);  }### Answer:
@Test public void allPositiveTest() { Vertex vertex0 = new Vertex(0, 8); Vertex vertex1 = new Vertex(1, 9); Vertex vertex2 = new Vertex(2, 20); Vertex vertex3 = new Vertex(3, 12); List<Vertex> vertices = Arrays.asList(vertex0, vertex1, vertex2, vertex3); Set<Vertex> ans = new HashSet<>(); Assert.assertEquals(49, MaxWeightClosure.solve(vertices, ans)); System.out.println(ans); }
@Test public void allNegativeTest() { Vertex vertex0 = new Vertex(0, -8); Vertex vertex1 = new Vertex(1, -9); Vertex vertex2 = new Vertex(2, -20); Vertex vertex3 = new Vertex(3, -12); vertex1.addEdge(vertex0); vertex2.addEdge(vertex0); vertex3.addEdge(vertex0); List<Vertex> vertices = Arrays.asList(vertex0, vertex1, vertex2, vertex3); Set<Vertex> ans = new HashSet<>(); Assert.assertEquals(0, MaxWeightClosure.solve(vertices, ans)); System.out.println(ans); }
@Test public void basicTest() { Vertex vertex0 = new Vertex(0, 8); Vertex vertex1 = new Vertex(1, -9); Vertex vertex2 = new Vertex(2, -20); Vertex vertex3 = new Vertex(3, 12); Vertex vertex4 = new Vertex(4, -10); Vertex vertex5 = new Vertex(5, 5); vertex0.addEdge(vertex1); vertex0.addEdge(vertex3); vertex1.addEdge(vertex4); vertex1.addEdge(vertex5); vertex3.addEdge(vertex4); vertex2.addEdge(vertex3); List<Vertex> vertices = Arrays.asList(vertex0, vertex1, vertex2, vertex3, vertex4, vertex5); Set<Vertex> ans = new HashSet<>(); Assert.assertEquals(7, MaxWeightClosure.solve(vertices, ans)); System.out.println(ans); }
@Test public void randomTest() { int V = 4; for (int i = 0; i < 150; i++) { if (i % 10 == 9) V++; List<Vertex> vertices = buildRandom(V); int expect = bruteForce(vertices); Set<Vertex> ans = new HashSet<>(); assertEquals(expect, MaxWeightClosure.solve(vertices, ans)); assertEquals(expect, check(ans, vertices)); System.out.println(ans); } }