題目：Flow Problem

?

網(wǎng)絡(luò)流深入學習請戳這里。

Ford-Fulkerson方法依賴于三種重要思想，這三個思想就是：殘留網(wǎng)絡(luò)，增廣路徑和割。

Ford-Fulkerson方法是一種迭代的方法。開始時，對所有的u，v∈V有f(u,v)=0，即初始狀態(tài)時流的值為0。在每次迭代中，可通過尋找一條“增廣路

徑”來增加流值。增廣路徑可以看成是從源點s到匯點t之間的一條路徑，沿該路徑可以壓入更多的流，從而增加流的值。反復進行這一過程，直至增廣路

徑都被找出來，根據(jù)最大流最小割定理，當不包含增廣路徑時，f是G中的一個最大流。

#include <stdio.h> #include <iostream> #include <string.h> #include <queue>const int N=1005;int pre[N]; //保存增廣路徑上的點的前驅(qū)頂點 bool vis[N]; int map[N][N]; //殘留網(wǎng)絡(luò)容量int s,t; //s為源點，t為匯點 int n,m;bool BFS() //找增廣路 {int i,cur;std::queue<int>Q;memset(pre,0,sizeof(pre));memset(vis,0,sizeof(vis));vis[s]=true; Q.push(s);while(!Q.empty()){cur=Q.front();Q.pop();if(cur==t) return true; //如果已達到匯點t，表明已經(jīng)找到一條增廣路徑，返回true.for(i=1;i<=n;i++){if(!vis[i]&&map[cur][i]) //只有殘留容量大于0時才存在邊{Q.push(i);pre[i]=cur;vis[i]=true;}}}return false; }int Max_Flow() {int i,ans=0;while(true){if(!BFS()) return ans; //如果找不到增廣路徑就返回。int Min=999999999;for(i=t;i!=s;i=pre[i]) //通過pre[]數(shù)組查找增廣路徑上的邊，求出殘留容量的最小值。Min=std::min(Min,map[pre[i]][i]);for(i=t;i!=s;i=pre[i]){map[pre[i]][i]-=Min;map[i][pre[i]]+=Min;}ans+=Min;} }int main() {int T,k=1;int u,v,c;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);s=1; t=n;memset(map,0,sizeof(map));while(m--){scanf("%d%d%d",&u,&v,&c);map[u][v]+=c;}printf("Case %d: %d\n",k++,Max_Flow());}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的hdu3549(网络流入门题-最大流的Ford-Fulkerson算法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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