[最大流]UVa820 - Internet Bandwidth

[最大流]UVa820 - Internet Bandwidth

传说中牛逼的网络流，刷了两道例题就刷不动了，还是要好好理解核心算法。

增广路算法的核心内容：参量网格中任意一条从s到t的有向道路都对应一条原图中的增广路。

求出能增的最大的值d。而且经证明是成立的。

所以就有一条类似结论的东西：

当且仅当参量网格中不存在s-t增广路时，此时的流是从s到t的最大流。

DFS很慢，于是就用到看BFS，此便是Edmonds-Karp算法，很多细节还是要好好理解的。

现在就是感觉自己好脑残的感觉，Wr了15次就是因为没有加\n

大家注意吧。

#include#define INF 0x7f7f7f7fconst int maxn = 10000;using namespace std;struct Edge{ int from,to,cap,flow; Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f) {}};struct EdmondsKarp{ int n,m; vector edges;//边数的两倍 vector G[maxn]; int a[maxn];//当起点到i的可改进量 int p[maxn]; //最短路上p的入弧编号 void init(int n){ for(int i=0;i Q; Q.push(s); a[s]=INF; while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=0;ie.flow){ p[e.to] = G[x][i];//p数组相当于记录了 e.to的入弧，卧槽是不是很啰嗦，但是我自己理解了 a[e.to] = min(a[x],e.cap-e.flow);//找到这一条路上残量最小值 Q.push(e.to); } } if(a[t]) break; } if(!a[t]) break; for(int u=t;u!=s;u=edges[p[u] ].from){ edges[p[u] ].flow += a[t]; edges[p[u]^1 ].flow -= a[t]; } flow += a[t]; } return flow; }};int main(){ int N,kase=0; while(~scanf("%d",&N)&&N){ int S,T,M; EdmondsKarp A; A.init(N*4+10); scanf("%d%d%d",&S,&T,&M); while(M--){ int U,V,W; scanf("%d%d%d",&U,&V,&W); A.AddEdge(U,V,W); }// if(kase>0) printf("\n"); printf("Network %d\n",++kase); printf("The bandwidth is %d.\n\n",A.Maxflow(S,T)); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。