解題關鍵：使用的挑戰(zhàn)程序設計競賽上的模板，第一道網(wǎng)絡流題目，效率比較低，且用不習慣的vector來建圖。

看到網(wǎng)上其他人說此題有重邊，需要注意下，此問題只在鄰接矩陣建圖時會出問題，鄰接表不會存在的，也體現(xiàn)了鄰接表的優(yōu)越性？

edge結構體的第三個變量為from的下標。

模板一：

#include<bits/stdc++.h> #define MAX_V 17 #define inf 0x3f3f3f3f using namespace std; typedef long long ll; int n,m,s,t; struct edge{int to,cap,rev; }; vector<edge>G[MAX_V]; bool used[MAX_V]; void add_edge(int from,int to,int cap){G[from].push_back((edge){to,cap,G[to].size()});G[to].push_back((edge){from,0,G[from].size()-1}); } int dfs(int v,int t,int f){if(v==t)return f;used[v]=true;for(int i=0;i<G[v].size();i++){edge &e=G[v][i];if(!used[e.to]&&e.cap>0){int d=dfs(e.to,t,min(f,e.cap));if(d>0){e.cap-=d;G[e.to][e.rev].cap+=d;return d;}}}return 0; }int max_flow(int s,int t){int flow=0;while(1){memset(used,0,sizeof used);int f=dfs(s,t,inf);if(f==0) return flow;flow+=f;}return flow; }int main(){int T,u,v,f;scanf("%d",&T);for(int ca=1;ca<=T;ca++){memset(G,0,sizeof G);scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&f);add_edge(u,v,f);}s=1,t=n;int ans=max_flow(s,t);printf("Case %d: %d\n",ca,ans);}return 0; }

?模板二：dinic，187ms，比第一個快，在層次圖上進行增廣，且進行了當前弧優(yōu)化。

#include<bits/stdc++.h> #define inf 0x3f3f3f3f #define MAX_V 17 using namespace std; typedef long long ll; struct edge{int to,cap,rev;};//終點，容量，反向邊 vector<edge>G[MAX_V]; int level[MAX_V],iter[MAX_V]; int n,m,s,t; void add_edge(int from,int to,int cap){G[from].push_back((edge){to,cap,G[to].size()});G[to].push_back((edge){from,0,G[from].size()-1}); } void bfs(int s){memset(level,-1,sizeof level);queue<int>que;level[s]=0;que.push(s);while(!que.empty()){int v=que.front();que.pop();for(int i=0;i<G[v].size();i++){edge &e=G[v][i];if(e.cap>0&&level[e.to]<0){level[e.to]=level[v]+1;que.push(e.to);}}} }int dfs(int v,int t,int f){if(v==t) return f;for(int &i=iter[v];i<G[v].size();i++){edge &e=G[v][i];if(e.cap>0&&level[v]<level[e.to]){int d=dfs(e.to,t,min(f,e.cap));if(d>0){e.cap-=d;G[e.to][e.rev].cap+=d;return d;}}}return 0; }int max_flow(int s,int t){int flow=0;while(1){bfs(s);if(level[t]<0) return flow;memset(iter,0,sizeof iter);int f;while((f=dfs(s,t,inf))>0){flow+=f;}}return flow; }int main(){int T,u,v,f;scanf("%d",&T);for(int ca=1;ca<=T;ca++){memset(G,0,sizeof G);memset(iter,0,sizeof iter);scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&f);add_edge(u,v,f);}s=1,t=n;int ans=max_flow(s,t);printf("Case %d: %d\n",ca,ans);}return 0; }

?

轉載于:https://www.cnblogs.com/elpsycongroo/p/7885811.html

總結

以上是生活随笔為你收集整理的[hdu3549]Flow Problem(最大流模板题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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