有 \(n\) 个 \(A\) 类节点， \(p\) 个 \(B\) 类节点， \(q\) 个 \(C\) 类节点。每个 \(A\) 与一个 \(B\) 和一个 \(C\) 构成一组匹配（每个 \(A\) 只能与给定的 \(B\) 、 \(C\) 匹配，且每个 \(B\) 、 \(C\)只能匹配一个 \(A\) ），求最大匹配数。
\(n,\ p,\ q\leq100\)
网络流
先建成 \(B\to A,\ A\to C\) 两个二分图匹配，然后中间每个 \(A\) 类节点拆点限制流量并继承。
代码
#includeusing namespace std;const int maxn = 410, maxm = 1e5 + 10, inf = INT_MAX;int N, k1, k2;int S, T, h[maxn], q[maxn], dis[maxn], cur[maxn];struct edges { int nxt, to, w; edges(int x = 0, int y = 0, int z = 0) : nxt(x), to(y), w(z) {}} e[maxm];void addline(int u, int v, int w) { static int cnt = 1; e[++cnt] = edges(h[u], v, w), h[u] = cnt; e[++cnt] = edges(h[v], u, 0), h[v] = cnt;}bool bfs() { memcpy(cur, h, sizeof h); memset(dis, -1, sizeof dis); int l = 1, r = 1; q[1] = S, dis[S] = 0; while (l <= r) { int u = q[l++]; for (int i = h[u]; i; i = e[i].nxt) { int v = e[i].to; if (dis[v] == -1 && e[i].w) { q[++r] = v, dis[v] = dis[u] + 1; if (v == T) return 1; } } } return 0;}int dfs(int u, int f) { if (u == T || !f) { return f; } int res = 0, tmp; for (int& i = cur[u]; i && f; i = e[i].nxt) { int v = e[i].to; if (dis[v] == dis[u] + 1 && e[i].w) { if (!(tmp = dfs(v, min(f, e[i].w)))) { dis[v] = 0; continue; } e[i].w -= tmp, e[i ^ 1].w += tmp, res += tmp, f -= tmp; } } return res;}int dinic() { int res = 0; while (bfs()) { res += dfs(S, inf); } return res;}int main() { scanf("%d %d %d", &N, &k1, &k2); S = N + N + k1 + k2 + 1, T = S + 1; for (int i = 1; i <= k1; i++) { addline(S, i, 1); } for (int i = 1; i <= k2; i++) { addline(N + N + k1 + i, T, 1); } for (int i = 1; i <= N; i++) { addline(k1 + i, N + k1 + i, 1); } for (int i = 1; i <= N; i++) { for (int j = 1, x; j <= k1; j++) { scanf("%d", &x); if (x) addline(j, k1 + i, 1); } } for (int i = 1; i <= N; i++) { for (int j = 1, x; j <= k2; j++) { scanf("%d", &x); if (x) addline(N + k1 + i, N + N + k1 + j, 1); } } printf("%d", dinic()); return 0;}