#include <stdio.h>
int n,np,nc,m;
int a[552][552];
int xm[552],chk[552];
int ans;
int front,end,queue[1001];

int min(int a,int b)
{
    if(a<b) return(a);
    else return(b);
}

int bfs()
{
    int v,u;
    while(front<=end)
    {
        u=queue[front];
        for(v=1;v<=n+1;v++)
        if(a[u][v]&&!chk[v])
        {
            chk[v]=1;
            xm[v]=u;
            queue[++end]=v;
            if(v==n+1)
            return(1);
        }
        front++;
    }
    return(0);
}

int maxflew()
{
    int tmp,t;
    chk[0]=1;
    front=1,end=1,queue[1]=0;
    while(bfs())
    {
        t=n+1,tmp=a[xm[t]][t];
        while(t!=0)
        {
            tmp=min(tmp,a[xm[t]][t]);
            t=xm[t];
        }
        t=n+1;
        while(t!=0)
        {
            a[xm[t]][t]-=tmp;
            a[t][xm[t]]+=tmp;
            t=xm[t];
        }
        ans+=tmp;
        memset(chk,0,sizeof(chk));
        front=1,end=1,queue[1]=0;
    }
}

int main()
{
    while(scanf("%d %d %d %d",&n,&np,&nc,&m)!=EOF)
    {
        memset(a,0,sizeof(a));
        int i,j,k;
        int u,v,z;
        for(i=1;i<=m;i++)
        {
            scanf(" (%d,%d)%d",&u,&v,&z);
            a[u+1][v+1]=z;
        }
        for(i=1;i<=np;i++)
        {
            scanf(" (%d)%d",&u,&z);
            a[0][u+1]=z;
        }
        for(i=1;i<=nc;i++)
        {
            scanf(" (%d)%d",&u,&z);
            a[u+1][n+1]=z;
        }
        ans=0;
        maxflew();
        printf("%d\n",ans);

//        for(i=0;i<=n+1;i++)
//        {
//            for(j=0;j<=n+1;j++)
//            printf("%d ",a[i][j]);
//            printf("\n");
//        }
    }
    return 0;
}

• Re: 求教，错哪了？ (17) yrleep 2012-03-30 11:12:20