PIGS
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 13677 | Accepted: 6044 |
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.
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.
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
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
Sample Output
7
这题难点在于如何建图,如何理解题目中的“if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.”也将成为建图的关键。
如果我们把每个顾客作为图中的点,则对于拥有某个猪圈的钥匙的连续的两个顾客i和j,建一条边i->j。现在解释为何可以这样建边:比如说i拥有猪圈1,2,3的钥匙,j拥有猪圈1的钥匙,这样i,j同时拥有3号猪圈的钥匙,按理说j只能打开1号猪圈,但i顾客购买猪后,Mirko是可以随意分配1,2,3中猪的数量的,所以j顾客实质上是可以得到1,2,3中的猪的。
因为猪圈有m个,所以我们可以加一个源点s,分别与n个顾客建边,鉴于上面的建边方式,s应与每个猪圈的第一个顾客建边,边容量为猪圈中猪的数量,若某个顾客同时为多个猪圈的第一个顾客,则数量相加。
每个顾客购买猪的数量是有上限的,所以我们应该引入一个汇点t,每个顾客与t建一条边,边容量为每个顾客需要购买的猪的数量。
#include <iostream> #include<cstdio> using namespace std; const int MAXN=105; const int INF=(1<<29); int flow[MAXN][MAXN];//容量限制 int dalta[MAXN];//改变量 int pre[MAXN]; int flag[MAXN];//标号 int m,n; int EK() { int i,maxflow=0; int queue[MAXN],front,rear; while(1) { front=rear=0; for(i=1;i<=n+1;i++) flag[i]=0; flag[0]=1; pre[0]=0; dalta[0]=INF; queue[rear++]=0; while(front!=rear&&!flag[n+1]) { int v=queue[front++]; for(i=1;i<=n+1;i++) { if(flag[i]) continue; if(flow[v][i]) { dalta[i]=min(dalta[v],flow[v][i]); flag[i]=1; pre[i]=v; queue[rear++]=i; } } } if(!flag[n+1]) break; maxflow+=dalta[n+1]; i=n+1; while(i!=0) { flow[pre[i]][i]-=dalta[n+1]; flow[i][pre[i]]+=dalta[n+1]; i=pre[i]; } } return maxflow; } int main() { int i,j; int pigs[1005];//每个猪圈中的猪的数量 int before[1005];//每个猪圈的前一个顾客 while(~scanf("%d%d",&m,&n)) { for(i=0;i<=n+1;i++) for(j=0;j<=n+1;j++) flow[i][j]=0; for(i=1;i<=m;i++) { scanf("%d",pigs+i); before[i]=-1; } for(i=1;i<=n;i++) { int num; scanf("%d",&num); while(num--) { scanf("%d",&j); if(before[j]==-1) { before[j]=i; flow[0][i]+=pigs[j]; } else { flow[before[j]][i]=INF; before[j]=i; } } scanf("%d",&j); flow[i][n+1]=j; } printf("%d\n",EK()); } return 0; }