程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1459 Power Network 最大流，模板題

poj 1459 Power Network 最大流，模板題

編輯：C++入門知識

終於開始網絡流了。EK算法很好懂。

這道題可以設一個超級源點指向所有普通源點，一個超級匯點被所有匯點指向，然後計算最大流就是答案要求的最大電力。

讀入太麻煩了可以用cin。不過…其實用輸入外掛的話又快又省事。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
//#define ll __int64
#define ll long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
int n,m,np,nc;
int p[200],flow[200][200],a[200],cap[200][200];
int s,t;    //超級源點和超級匯點
inline int ReadInt()
{
    char ch = getchar();
    int data = 0;
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    do
    {
        data = data*10 + ch-'0';
        ch = getchar();
    }while (ch >= '0' && ch <= '9');
        return data;
}
int ek()
{
    queue q;
    memset(flow,0,sizeof(flow));
    int f=0;
    for(;;)
    {
        memset(a,0,sizeof(a));
        a[s]=INF;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int v=0;v<=n+1;v++)
            {
                if(!a[v]&&cap[u][v]>flow[u][v])
                {
                    p[v]=u;
                    q.push(v);
                    a[v]=min(a[u],cap[u][v]-flow[u][v]);
                }
            }
        }
        if(a[t]==0) break;
        for(int u=t;u!=s;u=p[u])
        {
            flow[p[u]][u]+=a[t];
            flow[u][p[u]]-=a[t];
        }
        f+=a[t];
    }
    return f;
}
int main()
{
    int x,y,z;
    char e;
    while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
    {
        memset(cap,0,sizeof(cap));
        t=s=n;t++;
        for(int i=1;i<=m;i++)
        {
            x=ReadInt();
            y=ReadInt();
            z=ReadInt();;
            cap[x][y]=z;
        }
        for(int i=1;i<=np;i++)
        {
            x=ReadInt();
            y=ReadInt();
            cap[s][x]=y;        //超級源點連向所有普通源點
        }
        for(int i=1;i<=nc;i++)
        {
            cin>>e>>x>>e>>y;    //所有普通匯點連向超級匯點
            cap[x][t]=y;
        }
        printf("%d\n",ek());
    }
    return 0;
}