首页 > 代码库 > poj 1149 -- PIGS

poj 1149 -- PIGS

2024-07-13 02:16:48   220人阅读

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

3 33 1 102 1 2 22 1 3 31 2 6

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\n",ans);117         edges.clear();118         for(int i = 0; i < MaxN; i++)119             G[i].clear();120     }121     return 0;122 }
View Code

 


　　


联系
我们