网络最大流_Ford-Fulkerson算法

1,第一个数表示容量cij，第二个数表示流量fij
2,可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：
(1)容量约束：0≤fij≤cij，(vi,vj)∈E，
(2)守恒条件

3,可增广路径
所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。
设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
    (1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤fij<cij
    (2)在p上的所有后向弧(vi←vj)都是非零弧，即0<fij≤cij
则称p为(关于可行流f的)一条可增广路径。

4,最大流定理
当且仅当不存在关于f*的增广路径，可行流f*为最大流。

5,最大流算法
算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。

6,应用:http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
代码:(有环的情况存在)

#include <iostream>
#include <queue>

using namespace std;

const int maxN=201;

static int edge[maxN][maxN];
bool visited[maxN];
int father[maxN];
int N, M; //边数,顶点数
int ans; //结果
void Ford_Fulkerson( )
{

    while(1)
    {
        //一次大循环,找到一条可能的增广路径
        queue <int> q;
        memset(visited, 0, sizeof(visited));
        memset(father, -1, sizeof(father));
        int now;
        visited[0] = true;
        q.push(0);
        while(!q.empty())//广度优先
        {
            now = q.front();
            q.pop();
            if(now == M-1) break;
            for(int i = 0; i < M; i++)
            {
                //每次父亲节点都要更新,权值减为0的边就不算了.
                if(edge[now][i] && !visited[i])
                {
                    father[i] = now;
                    visited[i] = true;
                    q.push(i);
                }
            }
        }
        //可能的增广路不存在了
        if(!visited[M-1]) break;
        int u, min = 0xFFFF;
        for(u = M-1; u; u = father[u])//找出权值最小的边
        {
            if(edge[father[u]][u] < min)
                min = edge[father[u]][u];
        }
        //减去最小权值
        for(u = M-1; u; u = father[u])
        {
            //前向弧减去
            edge[father[u]][u] -= min;
            //后向弧加上
            //存在圆环,这句话关键
            edge[u][father[u]] += min;
        }
        //当前增广路径增加的流
        ans += min;
    }
}

int main()
{
    int s, e, w;
    while(cin >> N >> M)
    {
        ans = 0;
        memset(edge, 0, sizeof(edge));
        for(int i = 0; i<N; i++)
        {
            cin >> s >> e >> w;
            edge[s-1][e-1] += w;
        }
        Ford_Fulkerson();
        cout << ans << endl;
    }
    return 0;
}