如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入格式：
第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）
输出格式：
一行，包含一个正整数，即为该网络的最大流。
4 5 4 3 4 2 30 4 3 20 2 3 20 2 1 30 1 3 40
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
#include<cstdio> #include<cstring> #include<queue> #define R register using namespace std; int read(){ R int x=0;bool f=1; R char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return f?x:-x; } const int N=1e4+10; const int M=1e5+10; int n,m,S,T,head[N],cur[N],dis[N]; bool vis[N]; struct node{ int v,next,cap,flow; node(int v=0,int next=0,int cap=0,int flow=0){ this->v=v; this->next=next; this->cap=cap; this->flow=flow; } }e[M<<1];int tot=1; void add(int x,int y,int z){ e[++tot]=node(y,head[x],z,0); head[x]=tot; } bool bfs(){ memset(vis,0,sizeof vis); queue<int>q; q.push(S); vis[S]=1;dis[S]=0; while(!q.empty()){ int x=q.front();q.pop(); for(int i=head[x];i;i=e[i].next){ int v=e[i].v; if(!vis[v]&&e[i].cap>e[i].flow){ vis[v]=1; dis[v]=dis[x]+1; q.push(v); } } } return vis[T]; } int dfs(int x,int f){ if(x==T||!f) return f; int used=0,f1; for(int &i=cur[x];i;i=e[i].next){ if(dis[x]+1==dis[e[i].v]&&(f1=dfs(e[i].v,min(f,e[i].cap-e[i].flow)))){ e[i].flow+=f1;e[i^1].flow-=f1; used+=f1;f-=f1; if(!f) break; } } return used; } int dinic(){ int ans=0; while(bfs()){ for(int i=1;i<=n;i++) cur[i]=head[i]; ans+=dfs(S,0x7fffffff); } return ans; } int main(){ n=read();m=read();S=read();T=read(); for(int i=1,x,y,z;i<=m;i++){ x=read();y=read();z=read(); add(x,y,z); add(y,x,0); } printf("%d",dinic()); return 0; }
原文：http://www.cnblogs.com/shenben/p/6236147.html