最小费用最大流.cpp

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

/***************************************************
*   
*   Ek形式的最小费用最大流矩阵形式。
*   (poj	2516   Minimum Cost)
***************************************************/

int const MAXN = 256;//矩阵维数最大值
int const INF = 0xffffff;
int S, T;//源点、汇点。
int graph[MAXN][MAXN], flow[MAXN][MAXN], cost[MAXN][MAXN];
//容量矩阵、流量矩阵、费用矩阵
int pre[MAXN], dist[MAXN];
int EK()
{
    int i, j;
    int ans(0);
    //流量初始清空
    for (int i = 0; i <= T;i++)
        for (j = 0;j <= T;j++)
            flow[i][j] = 0;
    while (true)
    {
        for (i = 0; i <= T; i++)
            dist[i] = INF;
        dist[S] = 0;
        bool quit(false);
        do
        {//bellman-ford求增广路
            quit = true;
            for (i = 0; i < T; i++)
              for (j = 1; j <= T;j++)
                if (flow[i][j] < graph[i][j] && dist[i] + cost[i][j] < dist[j])
                {
                    dist[j] = dist[i] + cost[i][j];
                    pre[j] = i;
                    quit = false;
                }
        } while(!quit);
        if(dist[T] == INF) break;
        j = T;
        int Min = INF;
        j = T;
        while(j != S)
        {//找出最小增量
           i = pre[j];
           if(graph[i][j] - flow[i][j] < Min)
           Min = graph[i][j] - flow[i][j];
           j = i;
        }
        j = T;
        while (j!=S)
        {//沿路径增广
            i = pre[j];
            flow[i][j] += Min;
            flow[j][i] = -flow[i][j];
            j = i;
        }
        ans += Min * dist[T];
    }
    return ans;
}