pku 1459 Power Network(最大流 SAP)

解题思路

题意：

       一个电力网络是由电力运输线连接的一些节点（发电站(power station)，消费处(consumer)，调度器(dispatcher)）组成，发电站最多能产生出p[u]的电，消费处最多能消耗c[u]的电，调度器不产生也不消耗电，传输线最多能传送l[u,v]的电从节点u到v。让我们计算在这样一个网络中最大的电消耗量。

 

思路：

最大流问题，建图： 本来一共有n个结点（0 ….n-1），加上一个源点n指向每个power station，权为power station的p[u]; 加上一个汇点n+1，每个consumer指向它，权为consumer的c[u]。

然后只要求从源点到汇点的最大流就可以了。这几天学了两种算法，通过做这道题发现性能如下：

 

Ford-Fulkerson + cin = 1141ms

SAP(最短增广路算法) + cin = 313ms

SAP + scanf = 79ms  

 

感谢冰糖葫芦的模版http://www.icycandy.com/blog/template-of-broaden-the-shortest-path-algorithm/comment-page-1/#comment-1143

源程序

 

#include <stdio.h>
#include <string>
#include <queue>
#include <conio.h>
using namespace std;
#define N 105
#define inf 100000000
int g[N][N], d[N], num[N], pre[N];
int n, flow;

void init(int s, int t)
{
    queue<int> que;
    int k;
    que.push(t);
    memset(d, 1, sizeof(d));
    memset(num, 0, sizeof(num));
    d[t] = 0;
    num[0] = 1;

    while(que.empty() == 0)
    {
        k = que.front();
        que.pop();
        for(int i=0; i<n+2; i++)
        {
            if(d[i] >= n+2 && g[i][k] > 0)
            {
                d[i] = d[k] + 1;
                que.push(i);
                num[d[i]] ++;
            }
        }
    }
}

int find_path(int i)
{
    int j;
    for(j=0; j<n+2; j++)
    {
        if(g[i][j] > 0 && d[i] == d[j] + 1)
            return j;
    }
    return -1;
}

int relable(int i)
{
    int mm = inf;
    int j;
    for(j=0; j<n+2; j++)
    {
        if(g[i][j] > 0)
            mm = mm < d[j]+1 ? mm : d[j] + 1;
    }
    return mm == inf ? n : mm;
}

int max_flow(int s, int t)
{
    int flow = 0;
    int i, j, add, k;

    i = s;
    memset(pre, -1, sizeof(pre));
    while(d[s] < n+2)
    {
        j = find_path(i);
        if(j >= 0)
        {
            pre[j] = i;
            i = j;
            if(i == t)
            {
                add = inf;
                for(k=t; k!=s; k=pre[k])
                    add = add < g[pre[k]][k] ? add : g[pre[k]][k];
                for(k=t; k!=s; k=pre[k])
                {
                    g[pre[k]][k] -= add;
                    g[k][pre[k]] += add;
                }
                flow += add;
                i = s;
            }
        }
        else
        {
            int x = relable(i);
            num[x]++;
            num[d[i]]--;
            if(num[d[i]] == 0)
                return flow;
            d[i] = x;
            if(i != s)
                i = pre[i];
        }
    }
    return flow;
}

int main()
 {
    int i, j;
    int np, nc, m;
    int x, y, w;
    char ch;

    freopen("in.txt", "r", stdin);
    while(scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF)
    {
        memset(g, 0, sizeof(g));
        
        for(i=0; i<m; i++)
        {
            scanf(" (%d,%d)%d", &x, &y, &w);
            g[x][y] = w;
        }
        for(i=0; i<np; i++)
        {
            scanf(" (%d)%d", &x, &w);
            g[n][x] = w;
        }
        for(i=0; i<nc; i++)
        {
            scanf(" (%d)%d", &x, &w);
            g[x][n+1] = w;
        }
        init(n, n+1);
        flow = max_flow(n, n+1);
        printf("%d\n", flow);
    }
    getch();
    return 0;
}