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