题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入输出格式
输入格式：
第一行包含四个正整数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。
先讲一下dinic的思路。
与EK、FF相同，dinic也是通过找增广路来完成的。但与前两者不同的是，dinic是通过
bfs把图分层，再找多条路径长度相同的增广路，再重复操作。
另外，dinic找的增广路都是最短的，这样时间复杂度就会对？这可能比较玄学，具体的原理
和证明我也不太清楚。
下面是代码。
#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 head,next,to,b; }f[400000]; int tot,n,m,s,t; int mark[100000],dep[100000]; long long ans; void add(int u,int v,int w){ f[tot].next=f[u].head;f[u].head=tot;f[tot].to=v;f[tot].b=w;tot++; } bool bfs(){ memset(mark,0,sizeof(mark)); memset(dep,0,sizeof(dep)); queue<int>Q; Q.push(s); dep[s]=1; mark[s]=1; 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(mark[p]||!f[i].b) continue; mark[p]=1; dep[p]=dep[x]+1; Q.push(p); } if(mark[t]) return 1; } return 0; } int dfs(int x,int a){ if(x==t) return a; int flow=0; for(int i=f[x].head;i!=-1;i=f[i].next){ int p=f[i].to; if(dep[p]!=dep[x]+1||!f[i].b) continue; int delta=dfs(p,min(a,f[i].b)); flow+=delta; a-=delta; f[i].b-=delta; f[i^1].b+=delta; if(!a) break; } return flow; } void dinic(){ while(bfs()) ans+=dfs(s,INF); } 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); } dinic(); printf("%lld",ans); return 0; }
https://www.luogu.org/problem/show?pid=3376