PIGS
Time Limit: 1000ms
Memory Limit: 10000KB
This problem will be judged on PKU. Original ID: 64-bit integer IO format: %lld Java class name: Main 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 arives, 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
3 33 1 102 1 2 22 1 3 31 2 6
Sample Output
7
Source
解题:最大流问题。买猪。建图是关键啊!0为源n+1为汇。把买者看成流网络上的点,最先选择某个猪舍跟源点建立边,容量为这个猪舍猪头数,第二个选择某个猪舍的与第一个选择这个猪舍的买者建立边,容量为无穷大。类推。。。最后把最后与某个猪舍建立边的买者,再与汇建立边,数目为此买者的购买量!为什么这样建图呢?首先是源点!源点到第一个买者,我们考虑的不仅仅是第一个买者的购买力,还要考虑其他人的购买力,所以干脆把整个猪舍的猪都卖掉!假想可以卖完!至于中间的边,就是让尽可能的猪留给后面的人可以来买,但是最后的人的购买力有限,最多只能购买那么多!所以与汇邻接的边的权值为买者的购买量!最后流到汇的就是卖出的猪的头数。
之所以可以这样建图,是因为题意是指,第一个人打开某个猪舍后,这个猪舍就不会关了,这里面的猪可以随意卖给其他人。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #define LL long long11 #define INF 0x3f3f3f3f12 using namespace std;13 const int maxn = 1005;14 int n,m,a[maxn],p[maxn];15 int arc[maxn][maxn],pre[maxn],pigs[maxn];16 int bfs(){17 int u,v,f = 0;18 queue q;19 while(true){20 while(!q.empty()) q.pop();21 memset(a,0,sizeof(a));22 memset(p,0,sizeof(p));23 a[0] = INF;24 q.push(0);25 while(!q.empty()){26 u = q.front();27 q.pop();28 for(v = 0; v <= n+1; v++){29 if(!a[v] && arc[u][v] > 0){30 a[v] = min(a[u],arc[u][v]);31 p[v] = u;32 q.push(v);33 }34 }35 if(a[n+1]) break;36 }37 if(!a[n+1]) break;38 for(u = n+1; u; u = p[u]){39 arc[p[u]][u] -= a[n+1];40 arc[u][p[u]] += a[n+1];41 }42 f += a[n+1];43 }44 return f;45 }46 int main(){47 int i,j,k,buy,e;48 while(~scanf("%d%d",&m,&n)){49 memset(arc,0,sizeof(arc));50 memset(pre,0,sizeof(pre));51 for(i = 1; i <= m; i++)52 scanf("%d",pigs+i);53 for(i = 1; i <= n; i++){54 scanf("%d",&k);55 while(k--){56 scanf("%d",&e);57 if(pre[e]) arc[pre[e]][i] = INF;58 else arc[pre[e]][i] += pigs[e];59 pre[e] = i;60 }61 scanf("%d",&buy);62 arc[i][n+1] += buy;63 }64 cout< <