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