POJ1149 PIGS

PIGS

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 20759		Accepted: 9488

Description

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

Sample Output

Source

Croatia OI 2002 Final Exam - First day

暴力建图：
　　一看到题，最先想到的是要分层，以每个顾客为一层，该顾客可以打开的猪圈向该顾客连边，每层向下一层对应的猪圈以及能够相互之间调整的猪圈连边，求最大流。这样构图本身并没有错，但是数据范围是n<=100 m<=1000 图中的节点数会超过100000，时间上绝对不够

正确建图：

　　顾客之间连边.
　　新增源点s，汇点t，对于每个顾客来说，如果他是第一个打开某猪圈的，则从s向他连一条容量为该猪圈初始值的弧，如果与源点的流量已经不是0，则合并，如果不是第一个，则从上一个打开该猪圈的顾客向这个顾客连一条容量为+oo的弧，每个顾客向汇点连一条容量为该顾客希望购买的猪的数量的弧

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2250;
const int inf=0x3f3f3f3f;
struct edge{int v,cap,next;}e[N*8];int tot=1;
int n,m,k,S,T,cnt,head[N],last[N],dis[N],val[N],q[N*8];
void add(int x,int y,int z){
    e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;
    e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot;
}
void mapping(){
    S=0,T=m+k+1;n=m;
    for(int i=1,w;i<=m;i++){
        scanf("%d",&w);
        add(S,i,w);
        last[i]=i;
    }
    for(int i=1,w,v,cas;i<=k;i++){
        n++;
        for(scanf("%d",&cas);cas--;){
            scanf("%d",&v);
            add(last[v],n,inf);
            last[v]=n;
        }
        scanf("%d",&w);
        add(n,T,w);
    }
}
bool bfs(){
    for(int i=S;i<=T;i++) dis[i]=-1;
    int h=0,t=1;dis[S]=0;q[t]=S;
    while(h!=t){
        int x=q[++h];
        for(int i=head[x];i;i=e[i].next){
            if(dis[e[i].v]==-1&&e[i].cap){
                dis[e[i].v]=dis[x]+1;
                if(e[i].v==T) return 1;
                q[++t]=e[i].v;
            }
        }
    }
    return 0;
}
int dfs(int x,int f){
    if(x==T) return f;
    int used=0,t;
    for(int i=head[x];i;i=e[i].next){
        if(e[i].cap&&dis[e[i].v]==dis[x]+1){
            t=dfs(e[i].v,min(e[i].cap,f));
            e[i].cap-=t;e[i^1].cap+=t;
            used+=t;f-=t;
            if(!f) return used;
        }
    }
    if(!used) dis[x]=-1;
    return used;
}
void dinic(){
    int ans=0;
    while(bfs()) ans+=dfs(S,inf);
    printf("%d
",ans);
}
void init(){
    tot=1;
    memset(head,0,sizeof head);
}
int main(){
    while(scanf("%d%d",&m,&k)==2){
        init();
        mapping();
        dinic();
    }
    return 0;
}