Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 93263		Accepted: 36174

试题链接

文章目录

Description

Every time it rains on Farmer John’s fields, a pond forms over
Bessie’s favorite clover patch. This means that the clover is covered
by water for awhile and takes quite a long time to regrow. Thus,
Farmer John has built a set of drainage ditches so that Bessie’s
clover patch is never covered in water. Instead, the water is drained
to a nearby stream. Being an ace engineer, Farmer John has also
installed regulators at the beginning of each ditch, so he can control
at what rate water flows into that ditch. Farmer John knows not only
how many gallons of water each ditch can transport per minute but also
the exact layout of the ditches, which feed out of the pond and into
each other and stream in a potentially complex network. Given all this
information, determine the maximum rate at which water can be
transported out of the pond and into the stream. For any given ditch,
water flows in only one direction, but there might be a way that water
can flow in a circle.

Input

The input includes several cases. For each case, the first line
contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M
<= 200). N is the number of ditches that Farmer John has dug. M is the
number of intersections points for those ditches. Intersection 1 is
the pond. Intersection point M is the stream. Each of the following N
lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei
<= M) designate the intersections between which this ditch flows.
Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <=
10,000,000) is the maximum rate at which water will flow through the
ditch.

Output

For each case, output a single integer, the maximum rate at which
water may emptied from the pond.

Sample Input

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

Sample Output

50

题意：

n个边，m个点，其中点1是进水点，点m是出水点，每个边都有流水速率，问水流出的最大速率是多少？
题目样例分析如图：
1->4 流速为20
1->2->4 流速为20
1->2->3->4 流速为10
最终答案为50

题解：

典型的最大流问题
最大流的算法有很多，有FF算法，EK，Dinic，ISAP等
模板题，可以通过这个练练手入门
网络流非详细讲解

代码：

改了好几次终于改对了
题目中说的有好几组数据。。所以while读入
代码里面有比较详细的注释

Dinic做法

两个流程：
一个是bfs分层&&判断是否还有增广路
另一个dfs找最大流

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue> 
#define maxn 10001
#define INF 19260817
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
long long int cnt,cost[maxn],from[maxn],to[maxn],Next[maxn],head[maxn];
int level[maxn];//层数
queue<int>q;
int S,T,n,m;
void add(int x,int y,int z){
           //建边
    ++cnt;cost[cnt]=z;
    from[cnt]=x;to[cnt]=y;
    Next[cnt]=head[x];head[x]=cnt;
}
bool bfs(){
                            //bfs分层&&判断是否还有增广路 
    memset(level,-1,sizeof(level));
    level[S]=0;q.push(S);
    while(!q.empty()){
   
        int u=q.front();
		q.pop();
        for(int i=head[u];i!=-1;i=Next[i]){
   
            int v=to[i];
            if(cost[i]!=0&&level[v]==-1){
      //如果容量是0||已被更新 就不更新了
                level[v]=level[u]+1;//更新层数 
                q.push(v);
            }
        }
    }if(level[T]!=-1)return true;           //如果流不动了就结束dinic
    return false;
}
int dfs(int u,int flow){
               //dfs找最大流
    if(u==T)return flow;
    long long int ret=flow;                   //记录初始流量
    for(int i=head[u];i!=-1;i=Next[i]){
   
        if(ret<=0)break;            //如果已经没流了就退出
        int v=to[i];
        if(cost[i]!=0&&level[u]+1==level[v]){
   
            int k=dfs(v,min(cost[i],ret));  //把能流的都给下一个点
            ret-=k;
			cost[i]-=k;
			cost[i^1]+=k; //边权更新，剩余流量更新
        }
    }
    return flow-ret;                //返回流出的流量（总流量-剩余流量） 
}
int dinic(){
   
    int ans=0;
    while(bfs()==true){
   
        ans+=dfs(S,INF);            //累加最大流
    }
    return ans;
}
void init()
{
   
	mem(cost);
	mem(from);
	mem(to);
	mem(Next);
	mem(level);
	
}
int main(){
   
	while( ~scanf("%d%d",&m,&n))
	{
   
		init();初始化 
			cnt=1;
	    memset(head,-1,sizeof(head));
	  	if(!q.empty())
	  	{
   
	  		q.pop();
		}
	    S=1;//源点 
	    T=n;//始点 
	    for(int i=1;i<=m;i++){
   
	        int x,y,z;
	        scanf("%d%d%d",&x,&y,&z);
	        add(x,y,z);add(y,x,0);      //EK一样建边
	    }
	    printf("%d\n",dinic());
	}

}
//dinic时间复杂度:O(n^2 m).

EK做法

#include <cstdio>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
int const MAX = 1005;
int const inf = 0x3f3f3f3f;
int c[MAX][MAX];//c[u][v]保存容量
int f[MAX][MAX];//f[u][v]保存当前流量
int a[MAX];// a数组在每趟bfs中找到最小路径中最小残余流量的，a数组是个递推数组，a[v]的意思是从源点s到点v的最小残余流量、
//同时a数组还可以判断一个点是否遍历过 
int pre[MAX];//保存前一个点
int n, m;
int bfs(int s, int t)
{
   
    queue<int> q;
    int flow = 0;
    while(!q.empty())   q.pop();
    memset(f, 0, sizeof(f));
    while(1){
   
        memset(a, 0, sizeof(a));
        a[s] = inf;//将起始点的最小残余量设为最大
        q.push(s);
        while(!q.empty()){
   //bfs找到一条最短路，这里的边不代表距离，可以看作每两个点都是单位距离的
            int u;
            u = q.front();
            q.pop();
            for(int v = 1; v <= m; v++){
   //枚举所有点v <u,v>
                if(!a[v] && c[u][v] > f[u][v]){
   //a[]可以代替vis[]，来判断这个点是否已经遍历过，后面那个条件更是起了关键作用，很巧妙
                    pre[v] = u;
                    q.push(v);
                    a[v] = min(a[u], c[u][v] - f[u][v]);//递推
                }
            }
        }
        if(!a[t])   break;//直到最小残余流量为0时，退出
        
        for(int u = t; u != s; u = pre[u]){
   //更新增广路上的流量 
            f[pre[u]][u] += a[t];// 
            f[u][pre[u]] -= a[t];//反向边增加 
        }
        flow += a[t];//增加整个增广路的流量 
    }
    return flow;
}
 
int main()
{
   
    while(~scanf("%d %d", &n, &m)){
   
        memset(c, 0, sizeof(c));
        memset(pre, 0, sizeof(pre));
        for(int i = 1; i <= n; i++){
   
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            c[u][v] += w;
        }
        printf("%d\n", bfs(1, m));
    }
    return 0;
}