一、題目描述
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 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 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6
Sample Output
7
二、分析
這道題的見圖有些復雜，不過看到豬圈有1000個，而顧客有100個，可以發現不可能以豬圈為頂點。新設兩個頂點，一個s，一個t，當第一個顧客有個一個豬圈的鑰匙時，就有一條從s到該顧客的邊，容量為豬圈中豬的數量，以后另外有顧客有這個豬圈的鑰匙是，則有一條從前一個顧客到這個顧客的邊，容量為無窮大，同時每個顧客都有到t的邊，容量為顧客的需求量。求最大流，使用Relabel-To-Front算法，具體算法：最大流問題
三、代碼
1
#include<iostream>
2#include<list>
3using namespace std;
4#define MAXM 1001
5#define MAXN 101
6int s, t;
7int n, m;
8int pig[MAXM], record[MAXM];
9int c[MAXN+2][MAXN+2];
10int f[MAXN+2][MAXN+2];
11int e[MAXN+2];
12int h[MAXN+2];
13list<int> l;
14list<int>::iterator lit;
15list<int> neb[MAXN+2];
16list<int>::iterator nit[MAXN+2];
17void push(int u, int v)
18
{
19
int d = min(e[u], c[u][v] - f[u][v]);
20 f[u][v] += d;
21 f[v][u] = -f[u][v];
22 e[u] -= d;
23 e[v] += d;
24
}
25void relabel(int u)
26{
27 int mh = INT_MAX;
28 for(int i=0; i<n+2; i++)
29
{
30 if(c[u][i] > f[u][i])
31 mh = min(mh, h[i]);
32
}
33 h[u] = mh + 1;
34}
35void discharge(int u)
36{
37 while(e[u] > 0)
38 {
39 if(nit[u] == neb[u].end())
40 {
41 relabel(u);
42 nit[u] = neb[u].begin();
43 continue;
44 }
45 int v = *nit[u];
46 if(c[u][v] > f[u][v] && h[u] == h[v]+1)
47 push(u, v);
48 else
49 nit[u]++;
50 }
51}
52void init_preflow()
53{
54 memset(h, 0, sizeof(h));
55 memset(e, 0, sizeof(e));
56 h[s] = n+2;
57 for(int i=0; i<n+2; i++)
58 {
59 if(c[s][i] == 0)
60 continue;
61 f[s][i] = c[s][i];
62 f[i][s] = -f[s][i];
63 e[i] = c[s][i];
64 e[s] -= c[s][i];
65 }
66}
67void relabel_to_front()
68{
69 init_preflow();
70 for(int i=1; i<=n; i++)
71 {
72 l.push_back(i);
73 nit[i] = neb[i].begin();
74 }
75 lit = l.begin();
76 while(lit != l.end())
77 {
78 int u = *lit;
79 int old = h[u];
80 discharge(u);
81 if(h[u] > old)
82 {
83 l.erase(lit);
84 l.push_front(u);
85 lit = l.begin();
86 }
87 lit++;
88 }
89}
90int main()
91{
92 memset(c, 0, sizeof(c));
93 memset(f, 0, sizeof(f));
94 memset(record, -1, sizeof(record));
95 scanf("%d%d", &m, &n);
96 s = 0; t = n+1;
97 for(int i=1; i<=m; i++)
98 scanf("%d", &pig[i]);
99 for(int i=1; i<=n; i++)
100 {
101 int a, k, b;
102 scanf("%d", &a);
103 for(int j=0; j<a; j++)
104 {
105 scanf("%d", &k);
106 if(record[k] == -1)
107 {
108 if(c[s][i] == 0)
109 {
110 c[s][i] = pig[k];
111 neb[s].push_back(i);
112 neb[i].push_back(s);
113 }
114 else
115 c[s][i] += pig[k];
116 record[k] = i;
117 }
118 else
119 {
120 c[record[k]][i] = INT_MAX;
121 neb[record[k]].push_back(i);
122 neb[i].push_back(record[k]);
123 }
124 }
125 scanf("%d", &b);
126 c[i][t] = b;
127 neb[i].push_back(t);
128 neb[t].push_back(i);
129 }
130 relabel_to_front();
131 printf("%d\n", e[t]);
132}
posted on 2009-06-26 16:15
Icyflame 閱讀(1337)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告