P3376 【模板】网络最大流（EK算法）

贴上模版。

网络流真的很有意思，写最大流前必须要理解清楚增广等相关概念，推荐
oi wiki的讲解，潜心钻研一下相关证明。

EK算法大致思路：

①：在残留网络上不断找 $s$ 到 $t$ 的增广路，记路径上残留容量最小值为 $mn$。
②：给找到的增广路上的每条边上流量加 $mn$，给对应的反向边退掉 $mn$ 的流量。
③：重复①和②步骤，直到找不到增广路，则此时得到最大流 $|f|$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=10010;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}int n,m,S,T,head[N],tot=1,mf[N],pre[N];
struct node{int to,nxt,c;
}edge[N];
void add(int x,int y,int w){edge[++tot].to=y;edge[tot].c=w;edge[tot].nxt=head[x];head[x]=tot;
}bool bfs(){queue<int> q;memset(mf,0,sizeof(mf));mf[S]=1e9,q.push(S);while(!q.empty()){int t=q.front();q.pop();for(int i=head[t];i;i=edge[i].nxt){int y=edge[i].to;if(!mf[y]&&edge[i].c){mf[y]=min(mf[t],edge[i].c);q.push(y),pre[y]=i;if(y==T) return true;}}}return false;
}ll EK(){ll flow=0;while(bfs()){int v=T;while(v!=S){int i=pre[v];edge[i].c-=mf[T],edge[i^1].c+=mf[T],v=edge[i^1].to;}flow+=mf[T];}return flow;
}int main(){n=read(),m=read(),S=read(),T=read();for(int i=1;i<=m;i++){int x=read(),y=read(),w=read();add(x,y,w),add(y,x,0);}cout<<EK()<<endl;return 0;
}