POJ 3281 - Dining

貌似是目前找到最水的題目
但是因為太久沒寫程式了
腦袋整個打結 沒救

Description

有 $N$ 頭牛, $F$ 種食物, $D$ 種飲料
一頭牛是滿足的條件是他吃到喜歡的食物且喝到喜歡的飲料
求最多有多少頭牛是滿足的

Solution

原先的想法是: source → cow → food → drink → sink
每條邊的流量為 1

結果試了好久都是錯的
後來突然想到 food → drink 這個地方會錯
因為會發生某頭牛連到其他牛喜歡的飲料的情況發生

後來把模型改成: source → food → cow → cow → drink → sink
這裡把牛拆點的原因是為了防止重複使用的情形
接著做一次最大流就是答案了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define MAXN 105

using namespace std;

int N, F, D;
int st, ed;
vector< pair<int, int> > E;
vector<int> G[MAXN << 2];
int dep[MAXN << 2];

void addEdge(int, int, int);
int Dinic();
int BFS();
int DFS(int, int);

signed main()
{
IO;
cin >> N >> F >> D;
st = 0, ed = F + 2 * N + D + 1;
for (int i = 1, _f, _d, t; i <= N; i++) {
addEdge(F + i, F + N + i, 1);
cin >> _f >> _d;
for (int j = 0; j < _f; j++) {
cin >> t;
addEdge(t, F + i, 1);
}
for (int j = 0; j < _d; j++) {
cin >> t;
addEdge(F + N + i, F + 2 * N + t, 1);
}
}
for (int i = 1; i <= F; i++) {
addEdge(st, i, 1);
}
for (int i = 1; i <= D; i++) {
addEdge(F + 2 * N + i, ed, 1);
}
cout << Dinic() << endl;
return 0;
}

void addEdge(int u, int v, int w)
{
G[u].push_back(E.size());
E.push_back({v, w});
G[v].push_back(E.size());
E.push_back({u, 0});
}

int Dinic()
{
int mx = 0, flow;
while (BFS()) {
while ((flow = DFS(st, INT_MAX)))
mx += flow;
}
return mx;
}

int BFS()
{
queue<int> q;
memset(dep, 0, sizeof(dep));
dep[st] = 1;
q.push(st);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < (int)G[u].size(); i++) {
pair<int, int> cur = E[G[u][i]];
if (cur.second && !dep[cur.first]) {
dep[cur.first] = dep[u] + 1;
q.push(cur.first);
}
}
}
return dep[ed];
}

int DFS(int u, int flow)
{
if (u == ed)
return flow;
for (int i = 0; i < (int)G[u].size(); i++) {
pair<int, int> cur = E[G[u][i]];
if (dep[cur.first] == dep[u] + 1 && cur.second) {
int d = DFS(cur.first, min(flow, cur.second));
if (d) {
E[G[u][i]].second -= d;
E[G[u][i] ^ 1].second += d;
return d;
}
}
}
return 0;
}