网络流初步

一、网络流的定义

有向图 G = ( V, E )中：

•有唯一的一个源点S（入度为0：出发点）

•有唯一的一个汇点 T（出度为0：结束点）

•图中每条弧 (u, v) 都有一非负容量 c ( u, v )

满足上述条件的图G称为网络流图。

记为： G = ( V, E ，C)

1、可行流

◆每条弧 ( u, v )上给定一个实数f(u,v),满足：有 0 <= f ( u, v ) <= c( u, v ),则f(u,v)称为弧( u, v )上的流量。

◆如果有一组流量满足条件：

源点s ：流出量 = 整个网络的流量

汇点t ：流入量 =整个网络的流量

中间点：总流入量 = 总流出量

那么整个网络中的流量成为一个可行流。

2、最大流

•在所有的可行流中，流量最大的一个流的流量

如：图2中可行流7也是最大流。

•最大流可能不只一个。

二、最大流算法

◆Ford-Fulkerson （福特-福克森）算法：

步骤：
（1）如果存在增广路径,就找出一条增广路径

（2）然后沿该条增广路径进行更新流量（增加流量）

1、增广路径

•从 s 到 t 的一条简单路径，若边 ( u, v ) 的方向与该路径的方向一致，称 ( u, v ) 为正向边，方向不一致时称为逆向边。

若路径上所有的边满足：

①所有正向边有：f ( u, v ) < c ( u, v) 　　
②所有逆向边有：f ( u, v ) > 0

则称该路径为一条增广路径(可增加流量)

2、沿增广路径增广

1）先设d为为正无穷(可增加流，余流量)

若( u, v ) 是正向边

d = min ( d, c ( u, v ) – f (u, v ) )

若( u, v ) 是逆向边

d = min ( d, f ( u, v ) )

2）对与该增广路径上的边

若( u, v ) 是正向边，f ( u, v ) = f ( u, v ) + d;

若( u, v ) 是逆向边，f ( u, v ) = f ( u, v ) – d;

增广后，总流量增加了d

•定理：

可行流 f 为最大流，当且仅当不存在关于f 的增广路径

证：若 f 是最大流，但图中存在关于 f 的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f 是最大流矛盾。所以，最大流不存在增广路径。

◆Ford-Fulkerson方法(增广流)求最大流
（福特-福克森）

步骤：
（1）如果存在增广路径,就找出一条增广路径

DFS,BFS
（2）然后沿该条增广路径进行更新流量

（增加流量）

While 有增广路径 do 更新该路径的流量

迭代算法

算法的实现：

c [ u, v ]：容量

f [ u, v ]：流量

B[i]：保存找到的增广路径，记录路径上结点i的前驱结点。

Sum：最大流量。

假定：1是源点S；n是汇点T。

#include <iostream>
#include <algorithm>
#include <cstring>
#define OO 999999
using namespace std;

int c[100][100];//容量
int f[100][100];//流量
int b[100];     //增广路径前驱结点
int sum;
int n,m;

bool findflow(int k);
void addflow();

//找到k节点的后继节点i
bool findflow(int k)
{
    if (k==n) return true;//找到了一条增广路径
    for (int i=1;i<=n;i++)
    {
        if ( b[i]==-1 && (c[k][i]-f[k][i]>0||f[i][k]>0) )
        {
            b[i]=k;
            if ( findflow(i) ) return true;
        }
    }
    return false;
}

//沿增广路径增广
void addflow()
{
    int d=OO;
    int i=n;
    while ( b[i]!=0 )
    {
        if ( c[b[i]][i]>0 )
        {
            d=min(d,c[b[i]][i]-f[b[i]][i]);
        }
        if ( c[i][b[i]]>0 )
        {
            d=min(d,f[i][b[i]]);
        }
        i=b[i];
    }
    i=n;
    while ( b[i]!=0 )
    {
        if ( c[b[i]][i]>0 )
        {
            f[b[i]][i]+=d;
        }
        if ( c[i][b[i]]>0 )
        {
            f[i][b[i]]-=d;
        }
        i=b[i];
    }
    sum+=d;
}

int main()
{
    int x,y,z;
    cin >> n >> m;
    memset(c,-1,sizeof(c));
    memset(f,0,sizeof(f));
    for (int i=1;i<=m;i++)
    {
        cin >> x >> y >> z;
        c[x][y]=z;
    }
    for (int i=0;i<=n;i++) b[i]=-1;
    b[1]=0;
    while ( findflow(1) )
    {
        addflow();
        for (int i=0;i<=n;i++) b[i]=-1;
        b[1]=0;
    }
    cout << sum << endl;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (f[i][j]>0) cout << i << "-->" << j << " " << f[i][j] << endl;
        }
    }
    return 0;
}