POJ 3281 - Dining

http://poj.org/problem?id=3281

概要

F 種類の食べ物と D 種類の飲み物がある．

N の牛にはそれぞれ好みがあり，食べ物は f[i][0], ..., f[i][F[i]] のうちのいずれか，飲み物は d[i][0], ..., d[i][D[i]] のうちのいずれかを選びたい．

好みの食べ物と飲み物の両方を割り当てられる牛の頭数の最大値を答える．

ただし，同じ食べ物を2頭以上に割り当てることはできない．飲み物に関しても同様．

制約

• 1 <= F, D, N <= 100

解法

「ソース → 食べ物 → 牛 → 飲み物 → シンク」というグラフを作って最大流． 各エッジの容量はすべて1．

たとえばサンプル入力の場合，以下のようなグラフになる．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 static const int INF = 10000000;
 6 
 7 template <typename T>
 8 T edmonds_karp(const vector<vector<T> >& capacity, int source, int sink)/*{{{*/
 9 {
10   const int N = capacity.size();
11   vector<vector<T> > flow(N, vector<T>(N, 0));
12   T max_flow = 0;
13 
14   while (true) {
15     vector<int> parent(N, -1);
16     queue<int> q;
17     q.push(source);
18 
19     while (!q.empty() && parent[sink] < 0) {
20       const int v = q.front();
21       q.pop();
22 
23       for (int u = 0; u < N; u++) {
24         if (parent[u] < 0 && capacity[v][u] - flow[v][u] > 0) {
25           parent[u] = v;
26           if (u == sink) {
27             break;
28           }
29           q.push(u);
30         }
31       }
32     }
33 
34     if (parent[sink] < 0) {
35       break;
36     }
37 
38     T aug = INF;
39     for (int v = sink; v != source; v = parent[v]) {
40       const int u = parent[v];
41       aug = min(aug, capacity[u][v] - flow[u][v]);
42     }
43     max_flow += aug;
44     for (int v = sink; v != source; v = parent[v]) {
45       const int u = parent[v];
46       flow[u][v] += aug;
47       flow[v][u] -= aug;
48     }
49   }
50 
51   return max_flow;
52 }/*}}}*/
53 
54 int main()
55 {
56   int N, F, D;
57   scanf("%d %d %d", &N, &F, &D);
58   const int M = F + N + N + D + 2;
59   const int source = M-2, sink = M-1;
60   vector<vector<int> > c(M, vector<int>(M, 0));
61   for (int i = 0; i < F; i++) {
62     c[source][i] = 1;
63   }
64   for (int i = 0; i < N; i++) {
65     c[F+i][F+N+i] = 1;
66   }
67   for (int i = 0; i < D; i++) {
68     c[F+N+N+i][sink] = 1;
69   }
70 
71   for (int i = 0; i < N; i++) {
72     int n, m;
73     scanf("%d %d", &n, &m);
74     for (int j = 0; j < n; j++) {
75       int f;
76       scanf("%d", &f);
77       --f;
78       c[f][F+i] = 1;
79     }
80     for (int j = 0; j < m; j++) {
81       int d;
82       scanf("%d", &d);
83       --d;
84       c[F+N+i][F+N+N+d] = 1;
85     }
86   }
87 
88   printf("%d\n", edmonds_karp(c, source, sink));
89   return 0;
90 }