最大流模版 EK

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

#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);
}