Ford-Fulkerson算法

戳戳http://www.cnblogs.com/luweiseu/archive/2012/07/14/2591573.html

Ford-Fulkerson方法依赖于三种重要思想：残留网络，增广路径和割。

Ford-Fulkerson方法是一种迭代的方法。开始时，对所有的u，v∈V有f(u,v)=0，即初始状态时流的值为0。在每次迭代中，可通过寻找一条“增广路

径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直至增广路

径都被找出来，根据最大流最小割定理，当不包含增广路径时，f是G中的一个最大流。

代码：

#include <stdio.h>

#include <iostream>

#include <string.h>

#include <queue>

const int N=1005;

int pre[N];       //保存增广路径上的点的前驱顶点

bool vis[N];

int map[N][N];    //残留网络容量

int s,t;          //s为源点，t为汇点

int n,m;

bool BFS()        //找增广路

{

    int i,cur;

    std::queue<int>Q;

    memset(pre,0,sizeof(pre));

    memset(vis,0,sizeof(vis));

    vis[s]=true;    Q.push(s);

    while(!Q.empty())

    {

        cur=Q.front();

        Q.pop();

        if(cur==t) return true;       //如果已达到汇点t，表明已经找到一条增广路径，返回true.

        for(i=1;i<=n;i++)

        {

            if(!vis[i]&&map[cur][i])  //只有残留容量大于0时才存在边

            {

                Q.push(i);

                pre[i]=cur;

                vis[i]=true;

            }

        }

    }

    return false;

}

int Max_Flow()

{

    int i,ans=0;

    while(true)

    {

        if(!BFS()) return ans;     //如果找不到增广路径就返回。

        int Min=999999999;

        for(i=t;i!=s;i=pre[i])     //通过pre[]数组查找增广路径上的边，求出残留容量的最小值。

            Min=std::min(Min,map[pre[i]][i]);

        for(i=t;i!=s;i=pre[i])

        {

            map[pre[i]][i]-=Min;

            map[i][pre[i]]+=Min;

        }

        ans+=Min;

    }

}

int main()

{

    int T,k=1;

    int u,v,c;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        s=1; t=n;

        memset(map,0,sizeof(map));

        while(m--)

        {

            scanf("%d%d%d",&u,&v,&c);

            map[u][v]+=c;

        }

        printf("Case %d: %d\n",k++,Max_Flow());

    }

    return 0;

}