USACO Section 4.2: The Perfect Stall
10424 ワード
この問題の鍵は、問題を最大ストリームテンプレート問題に変換することです.まず、元の点、N個のcow個の点、M個のbarn点と一つの終点があり、元の点からcow点とbarn点から終点までの流れはすべて1であるが、cowに対応するbarnはcow点から対応するbarn点までの流れであり、1である.これで問題は元の点から終点までの最大ストリーム問題に変換された.
1 /*
2 ID: yingzho1
3 LANG: C++
4 TASK: stall4
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <stdio.h>
14 #include <queue>
15 #include <cstring>
16 #include <cmath>
17 #include <list>
18 #include <cstdio>
19 #include <cstdlib>
20 #include <limits>
21 #include <stack>
22
23 using namespace std;
24
25 ifstream fin("stall4.in");
26 ofstream fout("stall4.out");
27
28 const int MAX = 210;
29 const int INF = 2000000000;
30
31 int N, M;
32 int g[2*MAX][2*MAX], f[2*MAX][2*MAX], pre[2*MAX], inc[2*MAX];
33
34 bool bfs(int s, int d) {
35 queue<int> que;
36 for (int i = 1; i <= N+M+2; i++) pre[i] = -1;
37 que.push(s);
38 inc[s] = INF;
39 while (!que.empty()) {
40 int u = que.front();
41 que.pop();
42 for (int i = 1; i <= N+M+2; i++) {
43 if (pre[i] == -1 && f[u][i] < g[u][i]) {
44 inc[i] = min(inc[u], g[u][i]-f[u][i]);
45 pre[i] = u;
46 if (i == d) return true;
47 que.push(i);
48 }
49 }
50 }
51 return false;
52 }
53
54 int edmond_karp(int s, int d) {
55 int maxflow = 0;
56 while (bfs(s, d)) {
57 maxflow += inc[d];
58 for (int i = d; i != s; i = pre[i]) {
59 f[pre[i]][i] += inc[d];
60 f[i][pre[i]] -= inc[d];
61 }
62 }
63 return maxflow;
64 }
65
66 int main()
67 {
68 fin >> N >> M;
69 int s, d;
70 for (int i = 1; i <= N; i++) {
71 g[1][1+i] = 1;
72 fin >> s;
73 for (int j = 0; j < s; j++) {
74 fin >> d;
75 g[1+i][1+N+d] = 1;
76 }
77 }
78 for (int i = N+2; i <= N+M+1; i++) g[i][N+M+2] = 1;
79 fout << edmond_karp(1, N+M+2) << endl;
80
81 return 0;
82 }