链接http://www.cnblogs.com/longdouhzt/archive/2012/05/20/2510753.html
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <cstdlib> 5 #include <cmath> 6 #include <map> 7 #include <algorithm> 8 #include <list> 9 #include <ctime> 10 #include <set> 11 #include <string.h> 12 #include <queue> 13 using namespace std; 14 15 int maxData = 0x3fffffff; 16 17 int augment(int des, vector<int> pre, vector<vector<int> > path) { 18 if (pre[des] == -1) //残留图中不再存在增广路径 19 return -1; 20 else { 21 int res = maxData; 22 int cur_des = des; 23 int cur_pri = pre[des]; 24 while (cur_pri != -1) { 25 res = min(res, path[cur_pri][cur_des]); 26 cur_des = cur_pri; 27 if (pre[cur_pri] == -1) 28 break; 29 cur_pri = pre[cur_pri]; 30 } 31 return res; 32 } 33 } 34 int SPFA(int s, int des, vector<int> &pre, vector<vector<int> > path) { 35 int n = path.size(); 36 queue<int> myqueue; 37 int i; 38 vector<int> d(n, -1); 39 for (i = 0; i < n; ++i) { //初始化前驱 40 pre[i] = -1; 41 } 42 for (i = 0; i < n; ++i) { 43 d[i] = maxData; //将除源点以外的其余点的距离设置为无穷大 44 } 45 vector<bool> final(n, false); //记录顶点是否在队列中，SPFA算法可以入队列多次 46 vector<int> cnt(n, 0); //记录顶点入队列次数 47 d[s] = 0; //源点的距离为0 48 final[s] = true; 49 cnt[s]++; //源点的入队列次数增加 50 myqueue.push(s); 51 int topint; 52 while (!myqueue.empty()) { 53 topint = myqueue.front(); 54 myqueue.pop(); 55 final[topint] = false; 56 for (i = 0; i < n; ++i) { 57 if (d[topint] < maxData && d[i] > d[topint] + path[topint][i] 58 && path[topint][i] > 0) { 59 d[i] = d[topint] + path[topint][i]; 60 pre[i] = topint; 61 if (!final[i]) { //判断是否在当前的队列中 62 final[i] = true; 63 cnt[i]++; 64 if (cnt[i] >= n) //当一个点入队的次数>=n时就证明出现了负环。 65 return true; //剩余网络中不会出现负数，且单位费用相当于1,这种算法更适合最小费用最大流 66 myqueue.push(i); 67 } 68 } 69 } 70 } 71 return augment(des, pre, path); //返回增广路径的值 72 } 73 74 int BFS(int src, int des, vector<int>& pre, vector<vector<int> > capacity) { //EK算法使用BFS寻找增广路径 75 queue<int> myqueue; 76 int i; 77 int n = capacity.size(); //如果没错的话应该和pre的size一样 78 vector<int> flow(n, 0); //标记从源点到当前节点实际还剩多少流量可用 79 while (!myqueue.empty()) //队列清空 80 myqueue.pop(); 81 for (i = 0; i < n; ++i) { //初始化前驱 82 pre[i] = -1; 83 } 84 flow[src] = maxData; //初始化源点的流量为无穷大 85 myqueue.push(src); 86 while (!myqueue.empty()) { 87 int index = myqueue.front(); 88 myqueue.pop(); 89 if (index == des) //找到了增广路径 90 break; 91 for (i = 0; i < n; ++i) { //遍历所有的结点 92 if (i != src && capacity[index][i] > 0 && pre[i] == -1) { 93 pre[i] = index; //记录前驱 94 flow[i] = min(capacity[index][i], flow[index]); //关键：迭代的找到增量 95 myqueue.push(i); 96 } 97 } 98 } 99 if (pre[des] == -1) //残留图中不再存在增广路径 100 return -1; 101 else 102 return flow[des]; 103 } 104 int maxFlow(int src, int des, vector<vector<int> > capacity) { 105 106 int increasement = 0; //增广路径的值 107 int sumflow = 0; //最大流 108 int n = capacity.size(); 109 vector<int> pre(n, -1); //标记在这条路径上当前节点的前驱,同时标记该节点是否在队列中 110 while ((increasement = BFS(src, des, pre, capacity)) != -1) { 111 int k = des; //利用前驱寻找路径 112 while (k != src) { 113 int last = pre[k]; 114 capacity[last][k] -= increasement; //改变正向边的容量 115 capacity[k][last] += increasement; //改变反向边的容量 116 k = last; 117 } 118 sumflow += increasement; 119 } 120 return sumflow; 121 } 122 123 int main() { 124 vector<vector<int> > path(4, vector<int>(4, 0)); //记录残留网络的容量 125 vector<int> d(4, maxData); 126 for (int i = 0; i < 4; i++) 127 path[i][i] = maxData; 128 path[0][1] = path[1][0] = path[2][3] = 1; 129 path[1][2] = 5; 130 path[0][2] = 3; 131 path[1][3] = 2; 132 path[2][1] = 2; 133 path[0][3] = 3; 134 int sum = maxFlow(0, 3, path); 135 cout << sum; 136 return 0; 137 }