poj 1149 -- PIGS

PIGS

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 15747		Accepted: 7034

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

7

题意：有一养猪场，有m个猪圈，给出每个猪圈中猪的数量，来了n个买主，每个买主手中有若干猪圈的钥匙，且给出每个买主想要买多少猪。问，最多能卖出多少头猪。

思路：网络流最大流问题。第二个最大流的题目，建图比较麻烦。下面说说我的建图方式。

　　1. 我们将所有买主当成结点。那么除了买主外，还需两个点，一个源点一个汇点。我称之为supers,supert.
　　2. 将源点与每个猪圈的第一个买主建边，如有重复的可并，实现的时候我是用flag[]数组标记钥匙是否第一次出现，如果是则可建边，否则看 step 3.
　　3. 如果不是第一次出现，说明在这个买主之前有买主买猪。这时，在这两个买主之间建边，权值（也就是容量）为INF。实现时是用nodes[]数组记录前一个买主。
　　4. 将每个买主连向汇点。容量为次买主要买的猪数。

　　我的建图方式就是这样。。建完图后用Dinic 求解。

  1 /*======================================================================
  2  *           Author :   kevin
  3  *         Filename :   PIGS.cpp
  4  *       Creat time :   2014-07-20 15:11
  5  *      Description :
  6 ========================================================================*/
  7 #include <iostream>
  8 #include <algorithm>
  9 #include <cstdio>
 10 #include <cstring>
 11 #include <queue>
 12 #include <cmath>
 13 #define clr(a,b) memset(a,b,sizeof(a))
 14 #define MaxM 1005
 15 #define MaxN 105
 16 #define INF 0x7f7f7f7f
 17 using namespace std;
 18 struct Edge{
 19     int from,to,cap,flow;
 20 };
 21 vector<Edge> edges;
 22 vector<int>G[MaxN];
 23 bool vis[MaxN];
 24 int d[MaxN],cur[MaxN],supers,supert;
 25 bool BFS()
 26 {
 27     clr(vis,0);
 28     queue<int>Q;
 29     Q.push(supers);
 30     d[supers] = 0;
 31     vis[supers] = 1;
 32     while(!Q.empty()){
 33         int x = Q.front(); Q.pop();
 34         int len = G[x].size();
 35         for(int i = 0; i < len; i++){
 36             Edge& e = edges[G[x][i]];
 37             if(!vis[e.to] && e.cap > e.flow){
 38                 vis[e.to] = 1;
 39                 d[e.to] = d[x]+1;
 40                 Q.push(e.to);
 41             }
 42         }
 43     }
 44     return vis[supert];
 45 }
 46 int DFS(int x,int a)
 47 {
 48     if(x == supert || a == 0) return a;
 49     int flow = 0,f;
 50     int len = G[x].size();
 51     for(int& i = cur[x]; i < len; i++){
 52         Edge& e = edges[G[x][i]];
 53         if(d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap-e.flow))) > 0){
 54             e.flow += f;
 55             edges[G[x][i]^1].flow -= f;
 56             flow += f;
 57             a -= f;
 58             if(!a) break;
 59         }
 60     }
 61     return flow;
 62 }
 63 void AddEdge(int from,int to,int cap)
 64 {
 65     edges.push_back((Edge){from,to,cap,0});
 66     edges.push_back((Edge){to,from,0,0});
 67     int m = edges.size();
 68     G[from].push_back(m-2);
 69     G[to].push_back(m-1);
 70 }
 71 int Dinic(int s,int t)
 72 {
 73     int flow = 0;
 74     while(BFS()){
 75         clr(cur,0);
 76         flow += DFS(s,INF);
 77     }
 78     return flow;
 79 }
 80 int main(int argc,char *argv[])
 81 {
 82     int n,m,keys,k;
 83     int pighome[MaxM],  //猪圈中猪的数量
 84         nodes[MaxM],    //前一个买主的信息
 85         flag[MaxM];     //标记是否是买猪第一人
 86     while(scanf("%d%d",&n,&m)!=EOF){
 87         clr(pighome,0);
 88         clr(nodes,0);
 89         clr(flag,0);
 90         supers = 0;
 91         supert = m+1;
 92         for(int i = 1; i <= n; i++)
 93             scanf("%d",&pighome[i]);
 94         for(int i = 1; i <= m; i++){
 95             int sum = 0;
 96             scanf("%d",&keys);  //钥匙的数量
 97             for(int j = 0; j < keys; j++){
 98                 scanf("%d",&k);
 99                 if(!flag[k]){
100                     sum += pighome[k];  //合并重边
101                     flag[k] = 1;
102                 }
103                 else{
104                     if(nodes[k]){
105                         AddEdge(nodes[k],i,INF); //建买主之间的边
106                     }
107                 }
108                 nodes[k] = i;
109             }
110             AddEdge(supers,i,sum);  //添加合并后的边
111             int buy;
112             scanf("%d",&buy);
113             AddEdge(i,supert,buy);  //建立买主到汇点的边
114         }
115         int ans = Dinic(supers,supert);
116         printf("%d
",ans);
117         edges.clear();
118         for(int i = 0; i < MaxN; i++)
119             G[i].clear();
120     }
121     return 0;
122 }

View Code