本文共 3445 字，大约阅读时间需要 11 分钟。
链接
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 15 int maxData = 0x3fffffff; 16 17 int augment(int des, vector pre, vector > 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 &pre, vector > path) { 35 int n = path.size(); 36 queue myqueue; 37 int i; 38 vector 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 final(n, false); //记录顶点是否在队列中，SPFA算法可以入队列多次 46 vector 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 & pre, vector > capacity) { //EK算法使用BFS寻找增广路径 75 queue myqueue; 76 int i; 77 int n = capacity.size(); //如果没错的话应该和pre的size一样 78 vector 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 else102 return flow[des];103 }104 int maxFlow(int src, int des, vector > capacity) {105 106 int increasement = 0; //增广路径的值107 int sumflow = 0; //最大流108 int n = capacity.size();109 vector 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 > path(4, vector (4, 0)); //记录残留网络的容量125 vector 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 }
转载于:https://www.cnblogs.com/kakamilan/archive/2012/08/11/2634072.html