学步园

首先说一下，这个英语确实是不行了啊、、老靠翻译啊。不能在这么弄了啊、、得好好的做题了啊，要不以后会吃大亏的啊。。呜呜呜、、、

简述题意就是有很多的发电站与用户还有中转站。。发电站发电，用户耗电，然后求出一条最大流来、、由于有多个起点和会点所以加一个0，代表起点，n+1代表会点。

其实就是一个最大流问题的模板题、、、主要看懂题意建出图来就可以过了啊、、、

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <queue>
#define oo 1 << 30
#define N 500


using namespace std;


int map[N][N], v[N], link[N];
int n;


int EK()//找出所有可以到达的路径
{
    int i, sum = 0, now, min;
    queue <int> q;
    while(1)
    {
        memset(v , 0 , sizeof(v));
        memset(link , -1 , sizeof(link));
        while(!q.empty())
            q.pop();
        q.push(0);
        v[0] = 1;
        while(!q.empty())
        {
            now = q.front();
            q.pop();
            if(now == n+1)
                break;
            for(i = 0; i <= n+1; i++)
            {
                if(!v[i] && map[now][i] > 0)
                {
                    link[i] = now;
                    v[i] = 1;
                    q.push(i);
                }
            }
        }
        if(!v[n+1])
            break;
        min = oo;
        for(i = n+1; i != 0; i = link[i])//找到最细的那条路；
            if(map[link[i]][i] < min)
                min = map[link[i]][i];
        sum += min;
        for(i = n+1; i != 0; i = link[i])//更新所有边的余流，和已经使用的流量
        {
            map[link[i]][i] -= min;
            map[i][link[i]] += min;
        }
    }
    return sum;
}


int main()
{
    int np, nc, m, i;
    int u, v, w;
    char s;
    while(~scanf("%d %d %d %d",&n, &np, &nc, &m))
    {
        memset(map , 0 , sizeof(map));
        for(i = 0; i < m; i++)
        {
            cin >>s>>u>>s>>v>>s>> w;
            if(u != v)
                map[u+1][v+1] = w;
        }
        for(i = 0; i < np; i++)
        {
            cin >>s>>v>>s>>w;
            map[0][v+1] = w;
        }
        for(i = 0; i < nc; i++)
        {
            cin >>s>>u>>s>>w;
            map[u+1][n+1] = w;
        }
        printf("%d\n",EK());
    }
    return 0;
}