翻车笔记_ Dining晚餐 [最大流, 翻车]

翻车了翻车了…GG…GG

懵逼的 题目

传送至POJ
传送至菜(我)OJ

扯淡的 题解

一开始看成只要能吃到饮料或者肉(等等…奶牛吃肉????)就算满足…
Woc总部裸的二分图匹配嘛写写写…10min…Woc WA了????
要有肉有饮料艹艹艹艹艹艹艹艹

Emmmmm…既然有肉有饮料那就把肉和饮料串联在一块好了…
WAWAWA… 艹艹艹艹艹艹

Emmmm…这样好像会让饮料和肉被重复选? 拆点…
WAWAWA… 艹艹艹艹艹艹

调了1H+…
Woc不想了看题解…GG…拆奶牛…GG…往奶牛两边连肉和饮料…GG
因为在把饮料和肉串联的时候可能会出现被水淹没选了饮料之后选肉, 选完了以后肉并不是牛喜欢的…Emmmmmmmm…

自己菜, 无Fuck♂可说

沙茶的 代码

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXC (2000)
#define MAXN (1000000 + 5)
#define MAXM (2000000 + 5)
#define MAXF (1000)
#define INF (0x7ffffff)
#define rev(a) (((a - 1) ^ 1) + 1)
#define bhc(a) ((a) + MAXF)
#define bhcp(a) ((a) + MAXC)
#define bhd(a) ((a) + MAXC + MAXF)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from;
int to;
int next;
int cap;
int flow;
edg() {}
edg(int a, int b, int c, int d): from(a), to(b), next(c), cap(d), flow(0) {}
} b[MAXM << 1];
int cntb = 0;
int g[MAXN];

int dis[MAXN], ans;
bool bfs();
int dinic(int, int);
void solve();
void adn(int, int, int);
int main()
{
int nc, nf, nd;
scanf("%d%d%d", &nc, &nf, &nd);
for (int i = 1; i <= nd; i++)
{
adn(bhd(i), t, 1);
adn(t, bhd(i), 0);
}
for (int i = 1; i <= nf; i++)
{
adn(s, i, 1);
adn(i, s, 0);
}
for (int i = 1; i <= nc; i++)
{
adn(bhc(i), bhcp(i), 1);
adn(bhcp(i), bhc(i), 0);
}
int srd, srf[MAXF], srz;
for (int i = 1; i <= nc; i++)
{
scanf("%d%d", &srf[0], &srd);
for (int j = 1; j <= srf[0]; j++)
{
scanf("%d", &srf[j]);
adn(srf[j], bhc(i), 1);
adn(bhc(i), srf[j], 0);
}
for (int j = 1; j <= srd; j++)
{
scanf("%d", &srz);
adn(bhcp(i), bhd(srz), 1);
adn(bhd(srz), bhcp(i), 0);
}
}
solve();
printf("%d\n", ans);
return 0;
}
void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap);
g[from] = cntb;
}
bool bfs()
{
memset(dis, 0, sizeof(dis));
dis[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && (!dis[b[i].to]))
{
dis[b[i].to] = dis[dq] + 1;
q.push(b[i].to);
}
}
}
return dis[t];
}
void solve()
{
while (bfs())
{
ans += dinic(s, INF);
}
}
int dinic(int dq, int maxf)
{
if (dq == t || (!maxf))
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
{
int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
maxf -= zl;
re += zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
}
}
return re;
}

/*
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3
*/

By 神经病 Cansult