/** * nodes:网络的结点数 * edges:网络的边数 * s, t:分别为所求最大流的起点和终点 * network:邻接矩阵表示网络中当前的剩余流量 */ int nodes, edges; int s, t; // from 0 on int [][] network; // from 0 on
/** * flow:网络中的最大流量 * path:用数组表示每次寻找到的增广路径,初值为-1,长度为结点数(nodes) * 若能够在残余网络中(即network)通过DFS找到一条增广路径,则流量增加,然后更新残余网络 * 直到不能找到一条增广路径,根据最大流最小割原理,当前flow即为最大流量 * @return flow */ privateintmaxflow(){ int flow = 0; int [] path; //寻找一条增广路径 while (true) { path = newint [nodes]; if (dfs(path) == false) break; int min = Integer.MAX_VALUE / 2; for (int i = 0; i < nodes-1; i++) { if (path[i+1] == -1) break; min = Math.min(min, network[path[i]][path[i+1]]); } flow += min; for (int i = 0; i < nodes-1; i++) { if (path[i+1] == -1) break; network[path[i]][path[i+1]] -= min; network[path[i+1]][path[i]] += min; } } return flow; }
/** * 以非递归的方式进行DFS,使用数组模拟栈 * vis:用于标记访问过的结点 * flag:用于回溯 * 每次取path中最新的结点,若它为终点t,即找到了一条增广路径 * @param path:用于存储一条增广路径,每次dfs操作都赋初值-1 * @return 若能找到一条增广路径,返回true,否则返回false */ private boolean dfs(int [] path){ // assume s != t boolean [] vis = new boolean [nodes]; boolean flag; int n = 0, u; path[n++] = s; for (int i = 1; i < nodes; i++) { path[i] = -1; } while (n > 0) { u = path[n-1]; if (u == t) returntrue; vis[u] = true; flag = true; for (int i = 0; i < nodes; i++) { if (network[u][i] > 0 && !vis[i]) { path[n++] = i; flag = false; break; } } if (flag) path[--n] = -1; } returnfalse; }