求最大网络流总结

      一个有向图，每条边都有最大可能的数据传输量c，要求一个点到某个点一次能传输的最大数据量，即为求最大网络流，每条边实际的数据传输量称为流量。

基本思路：使用贪心算法，每次找出能使总流量更大的边，将数据向那条边流。

Ford-fulkerson算法

1. 读入所有有向边，并且加入流量为0的反向边
2. DFS查找所有点u的未被遍历的边(u,v)
3. 如果满足这条边流量大于0，更新这条边以及它的反向边的流量（同时会DFS遍历v点）
4. 重复2操作，直到所有点被遍历完成

算法复杂度：O(m+n)≈O(n^2)

Dinic算法

原理：利用BFS求最短路的方法将所有的边按从源点到汇点的距离排序，从而避免不必要的增广

1. BFS求源点到所有点的距离
2. DFS 遍历所有边(u,v)
3. 如果dis[v]==dis[u]+1且边的长度大于0，那么更新这条边以及它的反向边的流量（同时DFS遍历了v点）

用dis数组的好处：不仅减少了不必要的增广步骤，而且使增广顺序有序，不必记录点是否已被遍历

1. 重复2操作，直到没有符合条件的边为止

   算法复杂度：O(n^2*m)。（最坏情况，平均情况大大优于FF算法）

割

在网络中，将源点与汇点通过割边的方式划分成两个部分，割掉的所有边都是割，其中，s到t为正向割边，t到s为逆向割边

割的容量：所有正向割边的容量和

最小割：容量和最小的割

      定理1：如果f是网络中的一个流，那么f的流为割的正向边与逆向边容量之差

      定理二：如果f是一个流，CUT (S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割。

      推论：f的流量<=此流的割的容量

求最小割与求最大网络流等价

POJ 1273 Drainage Ditches

Description

Every time itrains on Farmer John's fields, a pond forms over Bessie's favorite cloverpatch. This means that the clover is covered by water for awhile and takesquite a long time to regrow. Thus, Farmer John has built a set of drainageditches so that Bessie's clover patch is never covered in water. Instead, thewater is drained to a nearby stream. Being an ace engineer, Farmer John hasalso installed regulators at the beginning of each ditch, so he can control atwhat rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transportper minute but also the exact layout of the ditches, which feed out of the pondand into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can betransported out of the pond and into the stream. For any given ditch, waterflows in only one direction, but there might be a way that water can flow in acircle.

Input

The input includesseveral cases. For each case, the first line contains twospace-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 intersectionspoints for those ditches. Intersection 1 is the pond. Intersection point M isthe stream. Each of the following N lines contains three integers, Si, Ei, andCi. Si and Ei (1 <= Si, Ei <= M) designate the intersections betweenwhich 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 throughthe ditch.

Output

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

Sample Input

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

Sample Output

50

题意

现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的点和所能流过的最大流量，

Ford-Fulkerson算法

#include
#include
#include
using namespace std;
const int MAX=600;
int first[MAX],nxt[MAX],go[MAX],flow[MAX],arcnum=1;
int vis[MAX];
void addarc(int a,int b,int c){//加边 
    nxt[++arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum]=b;
    flow[arcnum]=c;//记录该边容量 
}

int Dfs(int u,int t,int minc){//起点u，终点t，整条路径中流量最小为minc
    if(u==t) return minc;
    vis[u]=1;
    for(int p=first[u];p!=0;p=nxt[p]){
        int v=go[p];
        if(!vis[v]&&flow[p]>0){
            int f=Dfs(v,t,min(minc,flow[p]));
            if(f>0){
                flow[p]-=f;//正向边减去算出的流量 
                flow[p^1]+=f;//逆向边加上算出的流量
                /* n为任意偶自然数，那么n^1=n+1;(n+1)^1=n    */
                return f; 
            }
        }
    }
    return 0;//如果都不符合条件，返回0 
}

int MaxFlow(int s,int t){
    int ans=0;
    while(1){
        memset(vis,0,sizeof(vis));
        int f=Dfs(s,t,99999999);
        if(f<=0) return ans;
        ans+=f;
    }
}

int main()
{
//   freopen("in.txt","r",stdin);
    int n,m,a,b,c;
    while(scanf("%d%d",&m,&n)!=EOF){
        memset(first,0,sizeof(first));
        memset(flow,0,sizeof(flow));
        arcnum=1;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            addarc(a,b,c);//正向边流量为c 
            addarc(b,a,0);//逆向边流量为0 
        }
        printf("%d\n",MaxFlow(1,n));
    }
    
    return 0;
}