poj1459

题意大概

有n个发电站,m个用户,以及以及一些电力中转站。求电量最大消耗量

建图

典型的多源多汇题,所以加上一个超级源和超级汇,超级源和每个发电站之间连线,容量是发电站的电量

从每个用户向超级汇连线,容量是用户的消耗量

然后就直接可以用用模板解题了

//bnu1578 poj1459
//600k 63ms
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX=109;
const int INF=0xffffff;
int g[MAX][MAX];
int dis[MAX],pre[MAX],num[MAX];
int s,t,n,m;
int insert(int x,int y,int k)
{
    g[x+2][y+2]+=k;//防止有重边
    return 0;
}
int min(int a,int b){return  a<b?a:b;}
int bfs()
{
    queue<int>que;
    memset(dis,-1,sizeof(dis));
    memset(num,0,sizeof(num));
    que.push(t);
    dis[t]=0;
    num[0]=1;
    while(!que.empty())
    {
        int x=que.front();que.pop();
        for(int i=n;i>=0;i--)
        {
            if(g[i][x]==0||dis[i]!=-1) continue;
            dis[i]=dis[x]+1;
            que.push(i);
            num[dis[i]]++;
        }
    }
    return 0;
}
int isap()
{
    int ret=0,v=s;
    memset(pre,-1,sizeof(pre));
    bfs();
    while(dis[s]<n)
    {
        int flag=-1;
        for(int j=0;j<=n;j++)
        {
            if(g[v][j]>0 && dis[v]==dis[j]+1)
            {
                flag=j;
                break;
            }
        }
        if(flag>=0)
        {
            pre[flag]=v;
            v=flag;
            if(v==t)
            {
                int dt=INF;
                for(int j=t;j!=s;j=pre[j]) 
                    dt=min(dt,g[pre[j]][j]);
                for(int j=t;j!=s;j=pre[j])
                {
                    g[pre[j]][j]-=dt;
                    g[j][pre[j]]+=dt;
                }
                ret+=dt;
                v=s;
            }
        }
        else
        {
            int x=n;
            for (int j=0;j<=n;j++)
                if(g[v][j]>0 && dis[j]>=0) x=min(dis[j]+1,x);
            num[dis[v]]--;
            num[x]++;
            if(num[dis[v]]==0) return ret;
            dis[v]=x;
            if(v!=s) v=pre[v];
        }
    }
    return ret;
}
int main()
{
    int a1,a2,a3;
    int s1,s2,s3;
    char ss[10];
    while(scanf("%d%d%d%d",&n,&a1,&a2,&m)!=EOF)//m边的数量
    {
        memset(g,0,sizeof(g));
        for(int i=0;i<m;i++)
        {
            scanf(" (%d,%d)%d",&s1,&s2,&s3);
            insert(s1,s2,s3);
        }
        for(int i=0;i<a1;i++)
        {
            scanf(" (%d)%d",&s1,&s2);
            insert(-1,s1,s2);
        }
        for(int i=0;i<a2;i++)
        {
            scanf(" (%d)%d",&s1,&s2);
            insert(s1,n,s2);
        }
        s=1;
        n+=2;
        t=n;
        printf("%d\n",isap());
    }
    return 0;
}

模板链接