题目描述
如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。
输入输出格式
输入格式:
第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi,表示第i条有向边从ui出发,到达vi,边权为wi(即该边最大流量为wi)
输出格式:
一行,包含一个正整数,即为该网络的最大流。
输入输出样例
输入样例#1:
4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40
输出样例#1:
50
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=10,M<=25
对于70%的数据:N<=200,M<=1000
对于100%的数据:N<=10000,M<=100000
样例说明:
题目中存在3条路径:
4-->2-->3,该路线可通过20的流量
4-->3,可通过20的流量
4-->2-->1-->3,可通过10的流量(边4-->2之前已经耗费了20的流量)
故流量总计20+20+10=50。输出50。
EK和FF的区别在于EK求任意路径是用的是BFS,而FF是DFS,所以不得不说EK比FF快太多了。
(Dinic和ISAP:两个骑三轮的有什么好比的)
但EK的思路还是一样的,这里不再细讲。
#include<set> #include<map> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define INF 2147483647 using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct edge{ int next,to,head,b; }f[440000]; int n,m,s,t,tot; int a[20000],pre[440000],path[440000]; long long ans; void add(int u,int v,int w){ f[tot].next=f[u].head;f[u].head=tot;f[tot].b=w;f[tot].to=v;tot++; } void EK(){ ans=0; for(;;){ memset(a,0,sizeof(a)); memset(pre,0,sizeof(pre)); memset(path,0,sizeof(path)); queue<int> Q; Q.push(s); a[s]=INF; while(!Q.empty()){ int x=Q.front(); Q.pop(); for(int i=f[x].head;i!=-1;i=f[i].next){ int p=f[i].to; if(a[p]!=0||!f[i].b) continue; a[p]=min(a[x],f[i].b); pre[p]=x; path[p]=i; Q.push(p); } if(a[t]) break; } if(!a[t]) return; ans+=a[t]; for(int i=t;i!=s;i=pre[i]){ int x=path[i]; f[x].b-=a[t]; f[x^1].b+=a[t]; } } } int main(){ n=read();m=read();s=read();t=read(); for(int i=1;i<=n;++i) f[i].head=-1; for(int i=1;i<=m;++i){ int x,y,w;x=read();y=read();w=read(); add(x,y,w);add(y,x,0); } EK(); printf("%lld",ans); return 0; } //https://www.luogu.org/problem/show?pid=3376#sub