网络流算法

标号法过程为：
(1)　先将 flag、 prev 和 alpha 这 3 个数组各元素都初始化-1 。
(2)　将源点初始化为已标号未检查顶点，即 flag[0] = 0, prev[0] = 0, alpha[0] = INF， INF 表示无穷大；并将源点入队列。
(3)　当队列非空并且汇点没有标号，从队列头取出队列头顶点，设这个顶点为 v， v 肯定是已标号未检查顶点；因此，检查顶点 v 的正向和反向“邻接”顶点，如果没有标号并当前可以进行标号，则对这些顶点进行标号并入队列，这些顶点都是已标号未检查顶点；此后顶点 v 为已标号已检查顶点。反复执行这一步直至队列为空或汇点已获得标

测试数据:(6 表示顶点数, 10表示边数!)

6 10  
0 1 8 2
0 2 4 3
1 3 2 2
1 4 2 2
2 1 4 2
2 3 1 1
2 4 4 0
3 4 6 0
3 5 9 3
4 5 7 2

//////// 标号法求网络最大流.

#include <cstdio>
#include <cstring>
#include <cmath>

#define _clr(x, y) memset(x, y, sizeof(x))
#define Min(x, y) (x < y ? x : y)
#define INF 0x3f3f3f3f
#define N 1005
using namespace std;

struct ArcNode // 弧结构:c表示容量,f表示流量.
{
    int c, f;
};
ArcNode edge[N][N];
int queue[N]; // 队列
int flag[N]; // -1表示未检查未访问,0表示已访问未检查相邻顶点,1表示已访问已检查相邻顶点
int pre[N]; // 保存一个点的前驱.
int alpha[N]; //保存一个点的可改进量
int n;

int abs(int a)
{
    return a < 0 ? -a : a;
}

void ford()
{
    while(1)
    {
        //  初始化,
        int front=0, rear=0;
        _clr(flag, -1);
        _clr(pre, -1);
        _clr(alpha, -1);
        flag[0] = 0, pre[0] = 0, alpha[0] = INF;
        queue[rear++] = 0; // 把源点加入队列
        while(front<rear && flag[n-1]==-1) // 队列非空 且 汇点还未标号
        {
            int v = queue[front++];
            for(int i=0; i<n; i++)  // 检查顶点v的相邻顶点
            {
                if(flag[i]==-1)  // i点还未访问
                {
                    if(edge[v][i].c<INF && edge[v][i].f<edge[v][i].c) // 正向且流量未满
                    {
                        flag[i] = 0, pre[i] = v;
                        alpha[i] = Min(alpha[v], edge[v][i].c-edge[v][i].f);
                        queue[rear++] = i;
                    }
                    else if(edge[i][v].c<INF && edge[i][v].f)  // 反向 且 有流量
                    {
                        flag[i] = 0, pre[i] = -v;
                        alpha[i] = Min(alpha[v], edge[i][v].f);
                        queue[rear++] = i;
                    }
                }
            }
            flag[v] = 1;  // 加上源点流出量即是 最大流!
        }

        if(flag[n-1]==-1 || alpha[n-1]==0) break; // 汇点无法标号 或 得到的可改进量为0:即没有可改进路.

        // 进行调整后得到残留网络.
        int k1=n-1, k2=abs(pre[k1]);
        int a = alpha[n-1];
        while(1)
        {
            if(edge[k2][k1].f<INF)  // 正向加上可改进量
                edge[k2][k1].f += a;
            else  // 反向减去可改进量
                edge[k1][k2].f -= a;
            if(k2==0) break; // 直至到源点.
            k1 = k2, k2 = abs(pre[k1]);
        }
    }

    int MaxFlow=0;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            if(edge[i][j].f<INF)
            {
                printf("%d->%d: %d
", i,j,edge[i][j].f);  // 输出各条弧的实际流量
                if(i==0)
                    MaxFlow += edge[i][j].f;  // 加上源点流出量即是 最大流!
            }
    printf("MaxFlow: %d
", MaxFlow);
}
int main()
{
    int m, a, b, c, f;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                edge[i][j].c=edge[i][j].f = INF;
        while(m--)
        {
            scanf("%d%d%d%d", &a, &b, &c, &f);
            edge[a][b].c = c, edge[a][b].f = f;
        }
    puts("before test");
    ford();
    puts("after test");
    }
    return 0;
}

transform: none; white-space: normal;

Dinic
算法的具体步骤为：
(1) 初始化容量网络和网络流；
(2) 构造残留网络和层次网络，若汇点不在层次网络中，则算法结束；
(3) 在层次网络中用一次 DFS 过程进行增广， DFS 执行完毕，该阶段的增广也执行完毕；
(4) 转步骤(2)

#include <cstdio>
#include <cstring>

#define _clr(x, y) memset(x, y, sizeof(x))
#define Min(x, y) (x < y ? x : y)
#define INF 0x3f3f3f3f
#define N 1003
using namespace std;

int edge[N][N];
int queue[N], n;
int dist[N];

// 建立层次图
bool bfs()
{
    _clr(dist, -1);
    int front=0, rear=0;
    dist[1] = 0;
    queue[rear++] = 1;
    while(front < rear)
    {
        int u = queue[front++];
        for(int v=1; v<=n; v++)
        {
            if(dist[v]<0 && edge[u][v])
            {
                dist[v] = dist[u] + 1;
                queue[rear++] = v;
            }
        }
    }
    return dist[n]>0 ? 1:0;
}

// dfs代表一次增广,返回的是本次增广获得的可改进量.0表示没有增广路
int dfs(int u, int low)
{
    int a = 0;
    if(u==n) return low;
    for(int v=1; v<=n; v++)
    {
        //  u.v之间联通且满足层次条件约束且有曾广路存在
        if(edge[u][v] && dist[v]==dist[u]+1 && (a = dfs(v, Min(low, edge[u][v]))))
        {
            edge[u][v] -= a;
            edge[v][u] += a;
            return a;
        }
    }
    return 0;
}
int main()
{
    int m, a, b, c;
    while(~scanf("%d%d", &m, &n))
    {
        _clr(edge, 0);
        while(m--)
        {
            scanf("%d%d%d", &a, &b, &c);
            edge[a][b] += c;
        }
        int ans=0, a=0;
        while(bfs())  // 一直建立层次图,直到无法到达汇点为止.
            while(a = dfs(1,INF))  // 得到一条曾广路的可改进量.
                ans += a;
        printf("%d
",ans);
    }
    return 0;
}

一般预流推进算法

#include <cstdio>
#include <cstring>
#include <queue>
#define _clr(x, y) memset(x, y, sizeof(x))
#define Min(x, y) (x < y ? x : y)
#define INF 0x3f3f3f3f
#define N 1005
using namespace std;

int flow[N][N], h[N];
int E[N], n, MaxFlow, S, T;
queue<int> Q;

void Push(int &x)
{
    for(int i=1; i<=n; i++)
    {
        int tmp = Min(E[x], flow[x][i]);
        if(tmp>0 && (x==S || h[x]==h[i]+1))
        {
            flow[x][i] -= tmp, flow[i][x] += tmp;
            E[x] -= tmp, E[i] += tmp;
            if(i==T) MaxFlow += tmp;
            if(i!=T && i!=S) Q.push(i);
        }
    }
}

void Push_Relabel()
{
    MaxFlow = 0;
    S = 1, T=n;
    _clr(h, 0);
    _clr(E, 0);
    E[S]=INF, E[T]=-INF;
    h[S]=n;
    Q.push(S);
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        Push(x);
        if(x!=S && x!=T && E[x]>0)
        {
            h[x]++;
            Q.push(x);
        }
    }
    printf("%d
", MaxFlow);
}
int main()
{
    int m, a, b, c;
    while(~scanf("%d%d", &m, &n))
    {
        _clr(flow, 0);
        while(m--)
        {
            scanf("%d%d%d", &a, &b, &c);
            flow[a][b] += c;
        }
        while(!Q.empty()) Q.pop();
        Push_Relabel();
    }
    return 0;
}