RT,有巨佬能帮忙看一下吗?感谢
思路是:超级源点 0
-> 食物 1~f
-> 牛(入点) f+1~f+n
-> 牛(出点) f+n+1~f+2*n
-> 饮料 f+2*n+1~f+2*n+d
-> 超级汇点
代码如下,变量名尽量和题目中的差不多:
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int head[N], cnt = 0;
struct Edge {
int to, w, next;
} e[N << 1];
int n, f, d, lev[N];
int S, T;
inline void add(int u, int v, int w) {
e[++ cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
inline bool Bfs() {
queue<int> q;
for (int i = S; i <= T; ++ i) lev[i] = -1;
q.push(S); lev[S] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(e[i].w && lev[v] == -1) {
lev[v] = lev[u] + 1;
q.push(v);
if(v == T) return true;
}
}
}
return false;
}
inline int Dinic(int u, int flow) {
if (u == T)
return flow;
int res = 0, delta;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (e[i].w && lev[u] < lev[v]) {
delta = Dinic(v, min(e[i].w, flow - res));
if (delta) {
e[i].w -= delta;
e[i ^ 1].w += delta;
res += delta;
if(res == flow) break;
}
}
}
if(res != flow) lev[u] = -1;
return res;
}
int main() {
scanf("%d%d%d", &n, &f, &d);
S = 0;
T = f + 2 * n + d + 1;
for (int i = 1; i <= f; ++ i)
add(S, i, 1), add(i, S, 0);
for (int i = f + 2 * n + 1; i <= f + 2 * n + d; ++ i)
add(i, T, 1), add(T, i, 0);
for (int a1, a2, b, i = 1; i <= n; ++ i) {
add(f + i, f + n + i, 1);
add(f + n + i, f + i, 0);
scanf("%d%d", &a1, &a2);
for (int j = 1; j <= a1; ++ j) {
scanf("%d", &b);
add(b, f + i, 1); add(f + i, b, 0);
}
for (int j = 1; j <= a2; ++ j) {
scanf("%d", &b);
add(f + n + i, f + 2 * n + b, 1); add(f + 2 * n + b, f + n + i, 0);
}
}
int ans = 0;
while(Bfs())
ans += Dinic(S, INT_MAX);
printf("%d\n", ans);
return 0;
}