首页 > 代码库 > POJ 1149

POJ 1149

2024-07-12 08:16:35   221人阅读

PIGS
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 15724 Accepted: 7023

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

Source

Croatia OI 2002 Final Exam - First day
 
有M个猪圈，从源点到第一个打开每个猪圈的顾客连一条边，容量为猪圈的初始猪数，然后打开同一个猪圈的打开者，按照打开的顺序依次往下一个打开者连一条容量
为无穷大的边，每个顾客向汇点连一条容量为他想买的猪数的边，走最大流
 
  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <vector>  6 #include <queue>  7   8 using namespace std;  9  10 const int MAX_M = 1005; 11 const int MAX_N =105; 12 int M, N; 13 int pig[MAX_M]; 14 struct Edge {int from, to, cap, flow;}; 15 vector <int> p[MAX_M]; 16 int buy[MAX_N]; 17 vector <int> G[MAX_M]; 18 vector <Edge> edges; 19 int _max = 0; 20 int d[MAX_N]; 21 int cur[MAX_N]; 22 bool vis[MAX_N]; 23  24 void add_edge(int from, int to, int cap) { 25         edges.push_back((Edge) {from, to, cap, 0}); 26         edges.push_back((Edge) {to, from, 0, 0}); 27         int m = edges.size(); 28         G[from].push_back(m - 2); 29         G[to].push_back(m - 1); 30 } 31  32  33  34 void solve() { 35         for (int i = 1; i <= N; ++i) { 36                 add_edge(i, N + 1, buy[i]); 37         } 38  39         for (int i = 1; i <= M; ++i) { 40                 if (p[i].size()) { 41                         add_edge(0, p[i][0], pig[i]); 42                         for (int j = 0; j < p[i].size() - 1; ++j) { 43                                 add_edge(p[i][j], p[i][j + 1], _max); 44                         } 45                 } 46         } 47  48 } 49  50 bool BFS(int s, int t) { 51         memset(vis, 0, sizeof(vis)); 52         queue <int> q; 53         q.push(s); 54         d[s] = 0; 55         vis[s] = 1; 56         while (!q.empty()) { 57                 int x = q.front(); q.pop(); 58                 for (int i = 0; i < G[x].size(); ++i) { 59                         Edge &e = edges[ G[x][i] ]; 60                         if (!vis[e.to] && e.cap > e.flow) { 61                                 vis[ e.to ] = 1; 62                                 d[e.to] = d[x] + 1; 63                                 q.push(e.to); 64                         } 65                 } 66         } 67  68         return vis[t]; 69 } 70  71 int DFS(int x, int a, int t) { 72         if (x == t || a == 0) return a; 73         int flow = 0, f; 74         for (int &i = cur[x]; i < G[x].size(); ++i) { 75                 Edge &e = edges[ G[x][i] ]; 76                 if (d[x] + 1 == d[e.to] &&  (f = DFS(e.to, min(a, e.cap - e.flow), t))> 0) { 77                         e.flow += f; 78                         edges[ G[x][i] ^ 1].flow -= f; 79                         flow += f; 80                         a -= f; 81                         if (a == 0) break; 82                 } 83         } 84  85         return flow; 86 } 87  88 int Maxflow(int s, int t) { 89         int flow = 0; 90         while (BFS(s, t)) { 91                 memset(cur, 0, sizeof(cur)); 92                 flow += DFS(s, _max, t); 93         } 94  95         return flow; 96 } 97  98 int main() 99 {100     //freopen("sw.in", "r", stdin);101     scanf("%d%d", &M, &N);102     for (int i = 1; i <= M; ++i) {103             scanf("%d", &pig[i]);104             _max += pig[i];105     }106     for (int i = 1; i <= N; ++i) {107             int n;108             scanf("%d", &n);109             for (int j = 1; j <= n; ++j) {110                     int ch;111                     scanf("%d", &ch);112                     p[ch].push_back(i);113             }114             scanf("%d", &buy[i]);115     }116 117     solve();118     printf("%d\n", Maxflow(0, N + 1));119 120 121     //cout << "Hello world!" << endl;122     return 0;123 }
View Code

 


联系
我们