Power Network

时间：2010-06-12 来源：buptstehc

题目来源：Power Network
最大流问题。首先将多源多汇转换为单源单汇，即增加一个超级源点和超级汇点，超级源点到power station的线路容量为其发电量，consumer到超级汇点的线路容量为其耗电量，这样power station和consumer都转换成了dispatcher。接着采用Edmonds-Karp方法求最大流。

#include <stdio.h>

#define NODES 102
#define SOURCE 100
#define DEST 101
int cf[NODES][NODES], queue[NODES], head, tail, visited[NODES], p[NODES];

/*find an augmenting path*/
int bfs(void)
{
    int i, u, min, flag = 0;

    for(i = 0; i < NODES; i++)
        visited[i] = 0;
    visited[SOURCE] = 1;
    head = tail = 0;
    p[SOURCE] = -1;
    queue[tail++] = SOURCE;
    while(head != tail)
    {
        u = queue[head];
        head++;

        for(i = 0; i < NODES; i++)
        {
            if((cf[u][i] > 0) && (!visited[i]))
            {
                p[i] = u;
                if(DEST == i)
                {
                    flag = 1;
                    break;
                }
                queue[tail++] = i;
                visited[i] = 1;
            }
        }

        if(flag)
            break;
    }

    /*caculate the minimum residual value in the path*/
    if(flag)
    {
        min = cf[p[DEST]][DEST];
        i = p[DEST];
        while(p[i] != -1)
        {
            if(min > cf[p[i]][i])
                min = cf[p[i]][i];
            i = p[i];
        }
        return min;
    }
    return -1;
}

int main(void)
{
    int n, np, nc, m, i, j, u, v, z, cfp, sum;

    while(scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF)
    {
        sum = 0;
        for(i = 0; i < NODES; i++)
            for(j = 0; j < NODES; j++)
                cf[i][j] = 0;

        for(i = 0; i < m; i++)
        {
            scanf(" (%d,%d)%d", &u, &v, &z);
            cf[u][v] = z;
        }
        for(i = 0; i < np; i++)
        {
            scanf(" (%d)%d", &u, &z);
            cf[SOURCE][u] = z;
        }
        for(i = 0; i < nc; i++)
        {
            scanf(" (%d)%d", &u, &z);
            cf[u][DEST] = z;
        }

        /*Edmonds-Karp*/
        while((cfp = bfs()) != -1)
        {
            sum += cfp;
            i = DEST;
            while(p[i] != -1)
            {
                cf[p[i]][i] -= cfp;
                cf[i][p[i]] += cfp;
                i = p[i];
            }
        }

        printf("%d\n", sum);
    }

    return 0;
}