解題思路：

這是一道典型的模板題，直接套用EK算法即可。。。我感覺最大流的本質(zhì)就是能否找到一個從源點到匯點的增廣路徑，并將其最小的邊作為增加值，沿著增廣路上的邊進行更新。

AC:

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 200; const int inf = 0x7fffff; int n,m,s,t,map[maxn][maxn],path[maxn]; //map[i][j]存儲(i,j)的流，path存儲的是增廣路徑 int flow[maxn]; //flow存儲一次BFS遍歷之后流的可改進量int bfs() //尋找一條增廣路徑 {queue<int> q;memset(path,-1,sizeof(path));flow[s] = inf;q.push(s);while(!q.empty()){int now = q.front();q.pop();if(now == t) break;for(int i = 1; i <= m; i++){if(i != s && path[i] == -1 && map[now][i]){flow[i] = flow[now] < map[now][i] ? flow[now] : map[now][i];q.push(i);path[i] = now;}}}if(path[t] == -1) return -1; //找不到增廣路徑return flow[t]; }int Edmonds_Karp() {int max_flow = 0,step,now,pre;while((step = bfs()) != -1) //能夠找到一條增廣路徑{max_flow += step;now = t;while(now != s){pre = path[now];map[pre][now] -= step;map[now][pre] += step;now = pre;}}return max_flow; }int main() {while(cin>>n>>m){int u,v,cost;memset(map,0,sizeof(map));for(int i = 1; i <= n; i++){cin>>u>>v>>cost;map[u][v] += cost;}s = 1; t = m;printf("%d\n",Edmonds_Karp());}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1532（最大流）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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