发个网络流的标准代码,用的是BFS
外面自己套一个类就行了
capacity自己初始化放进去就可以了
返回值在max_flow里面,有需要的话可以自己改成返回类型的
1 public static final int WHITE = 0, GRAY = 1, BLACK = 2;
2 private int[][] flow, capacity, res_capacity;
3 private int[] parent, color, queue;
4 private int[] min_capacity;
5 private int size, source, sink, first, last;
6 private int max_flow;
7
8 private void maxFlow() // Edmonds-Karp algorithm with O(V3E) complexity
9 {
10 flow = new int[size][size];
11 res_capacity = new int[size][size];
12 parent = new int[size];
13 min_capacity = new int[size];
14 color = new int[size];
15 queue = new int[size];
16
17 for (int i = 0; i < size; i++)
18 for (int j = 0; j < size; j++)
19 res_capacity[i][j] = capacity[i][j];
20
21 while (BFS(source))
22 {
23 max_flow += min_capacity[sink];
24 int v = sink, u;
25 while (v != source)
26 {
27 u = parent[v];
28 flow[u][v] += min_capacity[sink];
29 flow[v][u] -= min_capacity[sink];
30 res_capacity[u][v] -= min_capacity[sink];
31 res_capacity[v][u] += min_capacity[sink];
32 v = u;
33 }
34 }
35 }
36
37 private boolean BFS(int source) // Breadth First Search in O(V2)
38 {
39 for (int i = 0; i < size; i++)
40 {
41 color[i] = WHITE;
42 min_capacity[i] = Integer.MAX_VALUE;
43 }
44
45 first = last = 0;
46 queue[last++] = source;
47 color[source] = GRAY;
48
49 while (first != last) // While "queue" not empty..
50 {
51 int v = queue[first++];
52 for (int u = 0; u < size; u++)
53 if (color[u] == WHITE && res_capacity[v][u] > 0)
54 {
55 min_capacity[u] = Math.min(min_capacity[v], res_capacity[v][u]);
56 parent[u] = v;
57 color[u] = GRAY;
58 if (u == sink) return true;
59 queue[last++] = u;
60 }
61 }
62 return false;
63 }