EK算法基于增廣路的思想,易于理解,但由于低效并不被經(jīng)常使用

#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> using namespace std; const int MAXN=10005,MAXM=100005; int n,m,s,flow,t,nume,head[MAXN],delta[MAXN],pre[MAXN]; queue<int> q; struct edge{int to,nxt,cap,flow; }e[MAXM<<1]; void adde(int from,int to,int cap){e[++nume].to=to;e[nume].cap=cap;e[nume].flow=0;e[nume].nxt=head[from];head[from]=nume; } int init(){int rv=0,fh=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') fh=-1;c=getchar();}while(c>='0'&&c<='9'){rv=(rv<<1)+(rv<<3)+c-'0';c=getchar();}return fh*rv; } int main(){n=init();m=init();s=init();t=init();for(int i=1;i<=m;i++){int u=init(),v=init(),cap=init();adde(u,v,cap);adde(v,u,0);}while(1){memset(delta,0,sizeof(delta));while(!q.empty()) q.pop();q.push(s);delta[s]=0x3f3f3f3f;pre[s]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(!delta[v]&&e[i].flow<e[i].cap){delta[v]=min(delta[u],e[i].cap-e[i].flow);pre[v]=i;q.push(v);}}if(delta[t]) break;}if(!delta[t]) break;for(int i=pre[t];i;i=pre[e[((i-1)^1)+1].to]){e[i].flow+=delta[t];e[((i-1)^1)+1].flow-=delta[t];}flow+=delta[t];}printf("%d\n",flow); }

轉(zhuǎn)載于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/8306371.html

總結(jié)

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

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