POJ 1459 Power Network 网络源基础题

POJ 1459 Power Network 网络流基础题

题意：

输入：N个点，N1个发电厂，N2个用电厂,M条路。

输入M条路，s,e,l.代表点s-e的容量是l。

输入N1个发电厂，s,l.代表s产生l的电。

输入N2个用电产，s,l，代表s用掉l的电。

Sample Input

2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)20
7 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7
         (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5
         (0)5 (1)2 (3)2 (4)1 (5)4

Sample Output

15
6

输入各种恶心。。。

思路：

网络流，最大流的模版题，今天刚开始看，学了一种新算法。Edmonds_Karp()，具体见http://blog.csdn.net/kdqzzxxcc/article/details/7881169

这道题还有一个需要处理的就是源点和汇点，因为有多源点和汇点，所以可以将0和N+1看成一个超级源点和超级汇点即可。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 105
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x)(x<<1|1)
using namespace std;

int Map[Max][Max];
int flow[Max];
int start,end;
int path[Max];
int q[Max*100];
int bfs()
{
    int n=end;
    flow[start]=inf;
    memset(path,-1,sizeof(path));
    path[start]=start;
    int num=0,cnt=0;
    q[num++]=start;
    while(num>cnt)
    {
        int temp=q[cnt++];
        if(temp==end)break;
        for(int i=0;i<=n;i++)
        {
            if(path[i]==-1&&Map[temp][i])
            {
                flow[i]=min(flow[temp],Map[temp][i]);
                q[num++]=i;
                path[i]=temp;
            }
        }
    }
    if(path[end]==-1)return -1;
    return flow[end];
}
int Edmonds_Karp()
{
    int max_flow=0,step,pre,now;
    while(1)
    {
        step=bfs();
        if(step==-1)return max_flow;
        now=end;
        max_flow+=step;
        while(now!=start)
        {
            pre=path[now];
            Map[pre][now]-=step;
            Map[now][pre]+=step;
            now=pre;
        }
    }
}
int main()
{
    int i,j,k,l,m,n1,n2,n;
    int s,e;
    while(scanf("%d %d %d %d",&n,&n1,&n2,&m)!=EOF)
    {
        memset(Map,0,sizeof(Map));
        while(m--)
        {
            scanf(" (%d,%d)%d",&s,&e,&l);
            Map[s+1][e+1]=l;
        }
        while(n1--)//将0看成超级源点
        {
            scanf(" (%d)%d",&s,&l);
            Map[0][s+1]=l;
        }
        while(n2--)//将N+1看成超级汇点
        {
            scanf(" (%d)%d",&s,&l);
            Map[s+1][n+1]=l;
        }
        start=0;
        end=n+1;
        printf("%d\n",Edmonds_Karp());
    }
    return 0;
}

继续研究网络流。。

POJ 1459 Power Network 网络源基础题

相关推荐