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

原文地址：https://blog.csdn.net/summ1ts/article/details/142595423

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！