POJ1459:Power Network（dinic)

浏览数：19 / 时间：2015年06月09日

题意：有n个结点，np个发电站，nc个消费者，m个电力运输线。接下去是m条边的信息(u,v)cost，cost表示边(u,v)的最大流量；a个发电站的信息(u)cost，cost表示发电站u能提供的最大流量；b个用户的信息(v)cost，cost表示每个用户v能接受的最大流量。
思路：在图中添加1个源点S和汇点T，将S和每个发电站相连，边的权值是发电站能提供的最大流量；将每个用户和T相连，边的权值是每个用户能接受的最大流量。从而转化成了一般的最大网络流问题，然后求解。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#define N 1100
#define inf 0x3f3f3f3f
typedef int ll;
using namespace std;
ll n,np,nc,m,tt,dis[N],head[N];
struct node
{
    ll x,y,w,next;
} eg[N*N];
void init()
{
    tt=0;
    memset(head,-1,sizeof(head));
}
void add(int xx,int yy,int ww)
{
    eg[tt].x=xx;
    eg[tt].y=yy;
    eg[tt].w=ww;
    eg[tt].next=head[xx];
    head[xx]=tt++;
    eg[tt].x=yy;
    eg[tt].y=xx;
    eg[tt].w=0;
    eg[tt].next=head[yy];
    head[yy]=tt++;
}
bool bfs(int s,int e)
{
    memset(dis,-1,sizeof(dis));
    dis[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int fa=q.front();
        q.pop();
        for(int i=head[fa]; i!=-1; i=eg[i].next)
        {
            int v=eg[i].y;
            if(dis[v]==-1&&eg[i].w)
            {
                dis[v]=dis[fa]+1;
                q.push(v);
            }
        }
    }
    if(dis[e]>0)
        return true;
    return false;
}
int dinic(int s,int maxt)
{
    if(s==n+1) return maxt;
    int a,sum=maxt;
    for(int i=head[s]; i!=-1; i=eg[i].next)
    {
        int v=eg[i].y;
        if(dis[v]==dis[s]+1&&eg[i].w>0)
        {
            a=dinic(v,min(sum,eg[i].w));
            eg[i].w-=a;
            eg[i+1].w+=a;
            sum-=a;
        }
    }
    return maxt-sum;
}
int main()
{
    ll xx,yy,ww;
    while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
    {
        init();
        while(m--)
        {
            while(getchar()!=‘(‘) ;
            scanf("%d,%d)%d",&xx,&yy,&ww);
            add(xx+1,yy+1,ww);
        }
        for(int i=0; i<np; i++)
        {
            while(getchar()!=‘(‘) ;
            scanf("%d)%d",&xx,&yy);
            add(0,xx+1,yy);
        }
        for(int i=0; i<nc; i++)
        {
            while(getchar()!=‘(‘) ;
            scanf("%d)%d",&xx,&yy);
            add(xx+1,n+1,yy);
        }
        ll ans=0;
        while(bfs(0,n+1))
        {
            ans+=dinic(0,inf);
        }
        printf("%d\n",ans);
    }
    return 0;
}