P2891 [USACO07OPEN] Dining G
大意
每一个小朋友在得到自己喜欢的饮料和食物的时候，就实现了其愿望，问最多能实现多少奶牛的愿望。
思路
首先我们考虑这样的三元关系 \((饮料，小朋友，食物)\)，这样的三元关系，如果我们直接在中间连边去跑最大流是否有问题呢？
显然是有问题的，如下图：
这样我们发现个奇怪的问题，一个小朋友对应的喜欢的食物和饮料其实是很多的，但是这样会使得不同的饮料与食物都对一个小朋友产生影响，现在我们需要做的是给一个点上约束，而这种技巧叫做拆点。
我们考虑将每个小朋友拆为 \(in\) 和 \(out\)，在 \(in\) 和 \(out\) 间连容量为 \(1\) 的边，这样我们就可以保证每个小朋友只被算一次，如下图：
在拆完点之后直接跑最大流即可。
代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX_N = 1000;
const int MAX_M = 100000;
struct edge {int v, c, next;
} e[MAX_M];
int p[MAX_N], eid;
void init() {memset(p, -1, sizeof(p));eid = 0;
}
void insert(int u, int v, int c) {e[eid].v = v;e[eid].next = p[u];e[eid].c = c;p[u] = eid++;
}
void addedge(int u, int v, int c) {insert(u, v, c);insert(v, u, 0);
}
int S, T;
int d[MAX_N];
bool bfs() {memset(d, -1, sizeof(d));queue<int> q;q.push(S);d[S] = 0;while (!q.empty()) {int u = q.front();q.pop();for (int i = p[u]; i != -1; i = e[i].next) {int v = e[i].v;if (e[i].c > 0 && d[v] == -1) {q.push(v);d[v] = d[u] + 1;}}}return (d[T] != -1);
}
int dfs(int u, int flow) {if (u == T) {return flow;}int res = 0;for (int i = p[u]; i != -1; i = e[i].next) {int v = e[i].v;if (e[i].c > 0 && d[u] + 1 == d[v]) {int tmp = dfs(v, min(flow, e[i].c));flow -= tmp;e[i].c -= tmp;res += tmp;e[i ^ 1].c += tmp;if (flow == 0) {break;}}}if (res == 0) {d[u] = -1;}return res;
}
int Dinic() {int res = 0;while (bfs()) {res += dfs(S, INF);}return res;
}
int main() {init();int n, m, k;cin >> n >> m >> k;for(int i = 1;i <= n;i ++){addedge(m + i, m + n + i, 1);int a, b; cin >> a >> b;for(int j = 0;j < a;j ++){int x; cin >> x;addedge(x, m + i, 1);}for(int j = 0;j < b;j ++){int x; cin >> x;addedge(m + n + i, m + 2 * n + x, 1);}}S = 0; T = m + 2 * n + k + 1;for(int i = 1;i <= m;i ++){addedge(S, i, 1);}for(int i = 1;i <= k;i ++){addedge(m + 2 * n + i, T, 1);}cout << Dinic() << endl;return 0;
}