发个网络流的标准代码,用的是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     }