最大流.cpp

本人参加ACM竞赛使用的一些算法模板

/************************************************************
*
*   最大流EK算法矩阵实现
*
*************************************************************/
#include <memory>
#include <cstdio>
#include <iostream>
using namespace std;
int const MAXN = 256;
int const INF = 0xffffff;
int N, S, T;//点数、源点、汇点
typedef int Graph[MAXN][MAXN];
typedef int Path[MAXN];
Graph graph, flow, R;
//容量网络、流量网络、残量网络
Path prev, visit, Q;
//前驱、记录是否被访问、广搜队列
int EK()
{
    memset(flow, 0, sizeof(flow) );//流量清空
    for (int i = 0; i < N; i++)
    {//初始残量网络等于原图
        copy(graph[i], graph[i] + N, R[i]);
    }
    for(; ;)
    {
        int head(0), tail(0);
        memset(visit, false, sizeof(visit));
        Q[tail++] = S;
        prev[S]   = -1;
        visit[S]  = 1;
        while (head < tail)
        {//BFS找增广路
            int k = Q[head++];
            int i;
            for (i = 0; i < N; i++)
            {
                if (!visit[i] && R[k][i] > 0)
                {
                    visit[i] = 1;
                    prev[i]  = k;
                    if (i == T) break;
                    if(tail >= 0) Q[tail++] = i;
                }
            }
            if(i == T) break;
        }
        if (!visit[T]) break;
        int c = INF;
        int j = T;
        while (j != S)
        {
            int i = prev[j];
            if(c > R[i][j]) c = R[i][j];
            j = i;
        }
        j = T;
        while (j != S)
        {//沿路增广
            int i = prev[j];
            flow[i][j] += c;
            flow[j][i] = -flow[i][j];
            R[i][j] = graph[i][j] - flow[i][j];
            R[j][i] = graph[j][i] - flow[j][i];
            j = i;
        }
    }
    int ans(0);
    for (int i = 0; i < N; i++)
    {//计算总流量
        ans += flow[S][i];
    }
    return ans;
}