最大流模板：

#include <iostream> #include <queue> //#include <conio.h> using namespace std; #define arraysize 201 int maxData = 0x7fffffff; int capacity[arraysize][arraysize]; //記錄殘留網(wǎng)絡(luò)的容量 int flow[arraysize]; //標(biāo)記從源點(diǎn)到當(dāng)前節(jié)點(diǎn)實(shí)際還剩多少流量可用 int pre[arraysize]; //標(biāo)記在這條路徑上當(dāng)前節(jié)點(diǎn)的前驅(qū),同時(shí)標(biāo)記該節(jié)點(diǎn)是否在隊(duì)列中 int n,m; queue<int> myqueue; int BFS(int src,int des) //EK算法使用BFS尋找增廣路徑 {int i,j;while(!myqueue.empty()) //隊(duì)列清空 myqueue.pop();for(i=1;i<m+1;++i) //初始化前驅(qū) {pre[i]=-1;}pre[src]=0;flow[src]= maxData; //初始化源點(diǎn)的流量為無(wú)窮大 myqueue.push(src);while(!myqueue.empty()){int index = myqueue.front();myqueue.pop();if(index == des) //找到了增廣路徑 break;for(i=1;i<m+1;++i) //遍歷所有的結(jié)點(diǎn) {if(i!=src && capacity[index][i]>0 && pre[i]==-1){pre[i] = index; //記錄前驅(qū) flow[i] = min(capacity[index][i],flow[index]); //關(guān)鍵：迭代的找到增量 myqueue.push(i); }}} if(pre[des]==-1) //殘留圖中不再存在增廣路徑 return -1;elsereturn flow[des]; } int maxFlow(int src,int des) {int increasement= 0;int sumflow = 0;while((increasement=BFS(src,des))!=-1){int k = des; //利用前驅(qū)尋找路徑 while(k!=src){int last = pre[k];capacity[last][k] -= increasement; //改變正向邊的容量 capacity[k][last] += increasement; //改變反向邊的容量 k = last;}sumflow += increasement;} return sumflow; }

總結(jié)

以上是生活随笔為你收集整理的最大流EK算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。