题目描述
如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。
输入格式
第一行包含四个正整数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。
题解：终于勉强弄懂网络流了！（可能我太弱了……）下面是详细解释版本！
#include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int oo=0x3f3f3f3f; const int N=10005; int cnt=1,n,m,s,t,u,v,w; struct node{ int next; int w; int v; int u; }e[2000005]; int head[N],d[N];//d表示深度 void add(int u,int v,int w){ cnt++; e[cnt].w=w; e[cnt].v=v; e[cnt].u=u; e[cnt].next=head[u]; head[u]=cnt; } //源点：只有流出去的点 //汇点：只有流进来的点 //流量：一条边上流过的流量 //容量：一条边上可供流过的最大流量 //残量：一条边上的容量-流量 bool bfs(){ memset(d,-1,sizeof(d)); queue<int>q; q.push(s); d[s]=0; while(!q.empty()){ int u=q.front(); q.pop();//正常走程序(BFS) for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(d[v]==-1 && e[i].w!=0){ d[v]=d[u]+1;//分层，即这个点在第几层里 q.push(v); } } } if(d[t]!=-1) return 1;//t被联通了 else return 0;//汇点深度不存在，说明不存在分层图，无增广路 } int dfs(int u,int f){//当前到达的点,和当前的流量 if(u==t) return f;//当前点到达了汇点,返回当前流量 for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(d[v]==d[u]+1 && e[i].w!=0){//是分层图 && 残量不为零(还可以再分配流量) //每一次由u推出v必须保证v的深度必须是u的深度+1 int ts=dfs(v,min(e[i].w,f));//向下增广 if(ts>0){//增广成功 e[i].w-=ts; // 正边减 e[i^1].w+=ts;// 反边加 return ts;//返回这次增广的值 } } } return 0; } int main(){ freopen("33367.in","r",stdin); freopen("33367.out","w",stdout); scanf("%d %d %d %d",&n,&m,&s,&t); for(int i=1;i<=m;i++){ scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,0); } int ans=0; while(bfs())//直到不存在增广路停止 ans+=dfs(s,oo);//oo使第一次dfs增广值为e[i].w,“灌满”第一条路 cout<<ans; return 0; }