<题目链接>
题目大意：
一个农夫他家的农田每次下雨都会被淹，所以这个农夫就修建了排水系统，还聪明的给每个排水管道设置了最大流量；首先输入两个数n,m ;n为排水管道的数量,m为节点的数量，接下来就是n行数，每一行分为x1,x2,x3；x1,x2为节点的序号,x3为流量；然后问从1号节点到m号节点的最大流是多少？
解题分析：
网络流最大流裸题，下面用的是EK算法，bfs起搜索增广路径的作用，EK算法比较难理解的地方就是反向边的构造。
#include <cstdio> #include <cmath> #include <queue> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int n,m; int map1[205][205]; int pre[205]; int vis[205]; int s,t; bool BFS() //bfs搜索增广路径 { int i,cur; queue<int>q; memset(pre,0,sizeof(pre)); memset(vis,0,sizeof(vis)); vis[s]=1; q.push(s); while(!q.empty()) { cur=q.front(); q.pop(); if(cur==t) return 1; //如果搜索到终点，说明搜到一条增广路,return 1; for(i=1; i<=n; i++) { if(!vis[i] &&map1[cur][i]) { q.push(i); pre[i]=cur; vis[i]=1; } } } return 0; //没有搜到一条完整的增广路 } int Max_flow() { int i,ans=0; while(1) { if(!BFS()) return ans; //如果找不到增广路径了，此时ans算得的就是最大流 int Min=0x3f3f3f3f; for(i=t; i!=s; i=pre[i]) //遍历该条增广路径 Min=min(Min,map1[pre[i]][i]); //找增广路径上的最小流量 for(i=t; i!=s; i=pre[i]) { map1[pre[i]][i]-=Min; //该条增广路径上的每条边都减去 min map1[i][pre[i]]+=Min; //该条增广路径上每条边修改反向边,反向边起到一种退流回溯的作用 } ans+=Min; } } int main() { while(scanf("%d %d",&m,&n)!=EOF) { memset(map1,0,sizeof(map1)); s=1,t=n; while(m--) { int u,v,c; scanf("%d%d%d",&u,&v,&c); map1[u][v]+=c; } printf("%d ",Max_flow()); } return 0; }
2018-08-14