@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); }
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(); }
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(); } }
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(); }  }
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); }
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);  }