POJ 1459 Power Network

最大流问题。

题意说电网有三种站点， 发电站，中转站，用户站。 直接建立超级S 和 T 。

S-> 发电站 容量就是发电量。用户-> T 容量就是用电量。

然后求最大流即可。

#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
#define acfun std::ios::sync_with_stdio(false)
using namespace std;

int n,np,nc,m;
struct lx
{
    int c,f;
};
lx g[301][301];
bool vis[301];
int path[301];
int flow[301];

void EK(int start,int thend)
{
    int maxflow=0;
    while(1)
    {
        for(int i=0;i<n+2;i++)
            vis[i]=0,path[i]=-1,flow[i]=0;
        queue<int>q;
        q.push(start);
        vis[start]=1,flow[start]=INF;
        while(!q.empty()&&!vis[thend])
        {
            int u=q.front();q.pop();
            for(int j=0;j<n+2;j++)
            {
                if(vis[j])continue;
                if(g[u][j].f<g[u][j].c)
                {
                    vis[j]=1;
                    path[j]=u;
                    flow[j]=min(flow[u],g[u][j].c-g[u][j].f);
                    q.push(j);

                }
                else if(g[j][u].f>0)
                {
                    vis[j]=1;
                    path[j]=u;
                    flow[j]=min(flow[u],g[j][u].f);
                    q.push(j);
                }
            }
        }
        if(!vis[thend]||flow[thend]==0)break;

        int v=thend,u=path[thend];
        int tmp=flow[thend];

        maxflow+=tmp;

        while(u!=-1)
        {
            if(g[u][v].f<g[u][v].c)
                g[u][v].f+=tmp;
            else
                g[v][u].f-=tmp;
            v=u,u=path[v];

        }
    }
    printf("%d\n",maxflow);
}

int main()
{
    while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
    {
        for(int i=0;i<n+2;i++)
            for(int j=0;j<n+2;j++)
            g[i][j].c=g[i][j].f=0;
        int u,v,c;
        char str[1001];
        while(m--)
        {
            scanf("%s",str);
            sscanf(str,"(%d,%d)%d",&u,&v,&c);
            g[u][v].c=c;

        }
        for(int i=0;i<np;i++)
        {
            scanf("%s",str);
            sscanf(str,"(%d)%d",&v,&c);
            g[n][v].c=c;
        }
        for(int i=0;i<nc;i++)
        {
            scanf("%s",str);
            sscanf(str,"(%d)%d",&u,&c);
            g[u][n+1].c=c;
        }
        EK(n,n+1);
    }
}

POJ 1459 Power Network,古老的榕树,5-wow.com