建图
我们可以看看如何建图。首先保证每一份食物和饮品都只使用过一次。
饿哦们可以把食物建在牛的 左边,饮品建在牛的右边。
食物连源点,饮品连汇点。这样就满足了。
但是还有一个要注意的地方。就是每一头牛只能用一次。
也就是说,我们每一头牛只能用一次。所以,要对牛进行拆点。
代码如下:
#include<iostream> #include<algorithm> #include<cstdio> #include<queue> #include<functional> using namespace std; const int inf = 2e9; const int max_n = 500; const int max_m = 21000; struct edge{ int to, cap, rev, next; }E[max_m << 2]; int head[max_n]; int cnt = 1; void add(int from, int to, int cap,int rev) { E[cnt].to = to;E[cnt].cap = cap; E[cnt].next = head[from];E[cnt].rev = rev; head[from] = cnt++; } int d[max_n]; bool searchpath(int s,int t) { queue<int> que;que.push(s); fill(d, d + max_n, -1);d[s] = 0; while (!que.empty()) { int u = que.front();que.pop(); for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (e.cap <= 0 || d[e.to] != -1)continue; d[e.to] = d[u] + 1; que.push(e.to); } }return d[t] != -1; } int iter[max_n]; int matchpath(int u,int t,int f) { if (u == t)return f; for (int& i = iter[u];i;i = E[i].next) { edge& e = E[i]; if (e.cap <= 0 || d[e.to] <= d[u])continue; int flow = matchpath(e.to, t, min(e.cap, f)); if (flow > 0) { e.cap -= flow; E[e.rev].cap += flow; return flow; } }return false; } int dinic(int s, int t) { int flow = 0;int f; while (searchpath(s, t)) { for (int i = 1;i < max_n;++i)iter[i] = head[i]; while (f = matchpath(s, t, inf)) flow += f; }return flow; } int N, F, D; int main() { scanf("%d %d %d", &N, &F, &D); for (int i = 1, Fi, Di;i <= N;++i) { scanf("%d %d", &Fi, &Di); for (int j = 1, food;j <= Fi;++j) { scanf("%d", &food); add(food + 2 * N, i, 1, cnt + 1); add(i, food + 2 * N, 0, cnt - 1); }for (int j = 1, drink;j <= Di;++j) { scanf("%d", &drink); add(i + N, drink + 2 * N + F, 1, cnt + 1); add(drink + 2 * N + F, i + N, 0, cnt - 1); } }int start = 2 * N + F + D + 1; int ed = start + 1; for (int i = 1;i <= N;++i) { add(i, i + N, 1, cnt + 1); add(i + N, i, 0, cnt - 1); }for (int i = 1;i <= F;++i) { add(start, i + 2 * N, 1, cnt + 1); add(i + 2 * N, start, 0, cnt - 1); }for (int i = 1;i <= D;++i) { add(i + 2 * N + F, ed, 1, cnt + 1); add(ed, i + 2 * N + F, 0, cnt - 1); }printf("%d", dinic(start, ed)); }