标签：pre CH Min int 网络 ri define
\(EK(Edmond—Karp)\)
洛谷日报 用最通俗的语言让你学会网络流
模板：P3376 【模板】网络最大流
点击查看代码
```
//EK
#include
#define cs const
#define il inline
#define ri register
#define pc(i) putchar(i)
using namespace std;typedef int I;typedef long long LL;LL FL,CH;templatebool in(T&a){for(FL=1;!isdigit(CH)&&CH!=EOF;CH=getchar())if(CH=='-')FL=-1;for(a=0;isdigit(CH);CH=getchar())a=a*10+CH-'0';return a*=FL,CH==EOF?0:1;}templateLL in(T&a,Args&...args){return in(a)+in(args...);}
#define int long long
cs int inf=1e9+8,N=1e5+9;
struct Pre{int v,e;}pre[N];
struct node{int to,w,nxt;}e[N<<1];
int n,m,s,t,top=1,h[N],inq[N];
il void add(cs int u,cs int v,cs int w){e[++top]={v,w,h[u]},h[u]=top;}
il bool bfs()//是否有增广路
{
queueq;
memset(inq,0,sizeof(inq));
inq[s]=1,q.push(s);
while(!q.empty())
{
int u=q.front(); q.pop();
for(ri int i=h[u],to;i;i=e[i].nxt)
if((!inq[to=e[i].to])&&e[i].w)
{
pre[to]={u,i};
if(to==t) return 1;
inq[to]=1,q.push(to);
}
}
return 0;
}
il int EK()
{
int ans=0;
while(bfs())
{
int Min=inf;
for(ri int i=t;i!=s;i=pre[i].v)
Min=min(Min,e[pre[i].e].w);
for(ri int i=t;i!=s;i=pre[i].v)
e[pre[i].e].w-=Min,e[pre[i].e^1].w+=Min;
ans+=Min;
}
return ans;
}
signed main()
{
in(n,m,s,t);
for(ri int i=1,u,v,w;i<=m;++i)
in(u,v,w),add(u,v,w),add(v,u,0);
printf("%lld",EK()); //qaq
return 0;
}
```
标签：pre,
CH,
Min,
int,
网络,
ri,
define
From： https://www.cnblogs.com/Bertidurlah/p/17183767.html