/*1149的建图比较巧妙，核心可以归为一句话：若第i个人与他后面的第j个人
有同一个猪圈的钥匙，则从i引边到j,容量为无穷大，其他按题意建图便可以了。*/

/*
起初我想建一个和课件里相似的图，再照上面说的在商人之间再引边，后来发现代码写起来难，
想到到，也写了下面这么多数组，后来看了网上说法，说可以把图构成最后只剩两个点，和商人，
动手一做 果然。。。。*/ 

/*1149 Accepted 712K 47MS G++ 2051B 2010-07-30 12:34:05 */

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
#define arr 103 
#define int_max 214748364
int S,T,M,N;
//下面圈起来的是起先错的。。。。。
/* 
// 这个网络流图仅有S，room，people，T四列； 
int map[1001][101];  //room-->people;
int map_add[101][101];  //people列有相同room钥匙的互相引边，容量为无穷大； 
int begin_flow[1001];  //S-->room，题目给出数据，是固定的;
int pre1[1001]={S};  //room列的前驱都是S; 
int pre2[101];  //people列的前驱； 
int  
//
//
int BFS()
{
    int i,j,k,v,u;
    memset(pre,-1,sizeof(pre));
    for(i=S;i<=T;i++) flow[i]=int_max;
    queue<int>que;
    pre[S]=0;
    que.push(S);
    while(!que.empty())
    {
        v=que.front();
        que.pop();
        for(i=1;i<=T;i++)
        {
            u=i;
            if(u==S||pre[u]!=-1||map[v][u]==0) continue;
            pre[u]=v;
            flow[u]=min(flow[v],map[v][u]);
            que.push(u);
        }
    }
    if(flow[T]==int_max) return -1;
    return flow[T];
}
int EK()
{
    int i,j,k,temp,now,last,ans=0;
    while(1)
    {
            if((temp=BFS())==-1) break;
            ans+=temp;
            now=T;  //T==sink,超级汇 
            while(now!=S) //S==source,超级源 
            {
                last=now; now=pre[now]; 
                map[now][last]-=temp; map[last][now]+=temp;
            }
    }
    return ans;
}
int main()
{
    int i,t,B,j,num;
    while(scanf("%d%d",&M,&N)!=EOF)
    {
        S=0; T=M+N+1;
        for(i=0;i<=M;i++)
            for(j=0;j<=N;j++)
                map[i][j]=map[j][i]=0;
        
        for(i=1;i<=M;i++)
        {
            scanf("%d",&begin_flow[i]);
            pre1[i]=S;
        }
        
        for(i=1;i<=N;i++)
        {
            scanf("%d",&num);
            for(j=1;j<=num;j++)
            {
                scanf("%d",&t);
                map[t][i]=int_max;
            }
            scanf("%d",&B);
            map[i][T]=B;
        }
        int ans=EK();
        printf("%d\n",ans);
    }
}*/
int room[1001],belong[1001],map[103][103],pre[103],flow[103];

int BFS()
{
    int i,j,k,v,u;
    for(i=S;i<=T;i++) flow[i]=int_max,pre[i]=-1;
    queue<int>que;
    pre[S]=0;
    que.push(S);
    while(!que.empty())
    {
           v=que.front();
           que.pop();
           for(u=1;u<=T;u++)
           {
               if(u==S||pre[u]!=-1||map[v][u]==0) continue;
               pre[u]=v;
               flow[u]=min(flow[v],map[v][u]);
               que.push(u);
           }
    }
    if(flow[T]==int_max) return -1;
    else return flow[T];
}
                     
        
    
int EK()
{
    int i,j,now,last,temp,ans=0;
    while(1)
    {
            if((temp=BFS())==-1) break;
            ans+=temp;
            now=T;
            while(now!=S)
            {
                 last=now; now=pre[now];
                 map[now][last]-=temp; map[last][now]+=temp;
            }
    }
    return ans;
}

int main()
{
    int i,j,t,num;
    while(scanf("%d%d",&M,&N)!=EOF)
    {
        S=0; T=N+1;
        memset(map,0,sizeof(map));
        for(i=1;i<=M;i++) scanf("%d",&room[i]),belong[i]=0;
        for(i=1;i<=N;i++)
        {
            scanf("%d",&num);
            for(j=1;j<=num;j++)
            {
                scanf("%d",&t);
                if(belong[t]==0)
                {
                    belong[t]=i;
                    map[S][i]+=room[t];
                }
                else
                {
                    map[belong[t]][i]=int_max;
                }
            }
            scanf("%d",&t);
            map[i][T]=t;
        }
        int ans=EK();
        printf("%d\n",ans);
    }
}

• Re:纪念一下，在北大oj里提交的第二道网络流题，AC代码贴上 (8) AcCry 2010-07-31 21:27:27
  • Re:纪念一下，在北大oj里提交的第二道网络流题，AC代码贴上 (76) yingxiang720 2011-02-06 21:57:57