在二分图最大匹配问题中，每个点最多只能和一条匹配边相关联。但是二分图多重匹配中，每个点可以多次匹配但是有匹配上限。
例题
Description
学校运动会即将开始，运动会有 $m$ 个项目，第 $i$ 个项目每个班必须派出 $p_i$ 名学生参加。班级里有 $n$ 名学生，第 $i$ 名学生最多参加 $a_i$ 个项目，并且他给出了他擅长的 $b_i$ 个项目的编号。求是否有一个合适的安排满足条件。
数据范围：$1\le n,m\le 100$。
Solution
我们把 $n$ 名学生和 $m$ 个项目看作是二分图的 $A,B$ 两部。那么每个学生向他擅长的项目连边。这就是二分图匹配的一般思想。
由于有 $a_i$ 和 $p_i$ 的限制，我们要求 $A$ 部的点关联的边不能超过 $a_i$ 个，那么我们需要一个方法来限制这个量在 $[0,a_i]$ 之间。这样一来，有没有感觉特别想网络流中的容量？
于是我们可以对二分图进行扩展，建立源点 $s$ 和汇点 $t$，在 $s$ 和 $A$ 部的第 $i$ 个点之间连一条容量为 $a_i$ 的边，在 $A$ 部和 $B$ 部之间相连的边的容量为 $1$，从 $B$ 部的第 $i$ 个点向 $t$ 连一条容量为 $p_i$ 的边。这个连边方式的正确性显然。
我们对这张图跑最大流，然后分析一下各个边的含义：
- 边 $(s,A_i)$ 表示学生 $A_i$ 参加的项目数量。
- 边 $(A_i,B_j)$ 表示 $A_i$ 是否参加了 $B_j$ 项目。
- 边 $(B_i,t)$ 表示项目 $B_i$ 的参加人数。
所以是否有合适方案，我们只要判断是否所有的边 $(B_i,t)$ 都满流即可！
时间复杂度：$\mathcal O((n+m)\cdot(nm)^2)$。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int N = 205, M = 5e4 + 5;
const int INF = 0x3f3f3f3f;
int n, m, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N];
int id(int p, int x) {
return p == 1 ? x : n + x;
}
void add(int u, int v, int w) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w;
}
void addedge(int u, int v, int w) {
add(u, v, w), add(v, u, 0);
}
int bfs(int s, int t) {
memset(dep, 0, sizeof(dep));
memcpy(cur, lnk, sizeof(lnk));
std::queue<int> q;
q.push(s), dep[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (val[i] && !dep[v]) {
q.push(v), dep[v] = dep[u] + 1;
}
}
}
return dep[t];
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
int ans = 0;
for (int i = cur[u]; i && ans < flow; i = nxt[i]) {
int v = ter[i];
if (val[i] && dep[v] == dep[u] + 1) {
int x = dfs(v, t, std::min(val[i], flow - ans));
if (x) {
val[i] -= x, val[i ^ 1] += x, ans += x;
}
}
}
if (ans < flow) dep[u] = -1;
return ans;
}
void dinic(int s, int t) {
while (bfs(s, t)) while (dfs(s, t, INF));
}
int main() {
scanf("%d%d", &n, &m);
int s = 0, t = n + m + 1;
for (int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
addedge(id(2, i), t, x);
}
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
addedge(s, id(1, i), x);
for (int k = 1; k <= y; k++) {
int j;
scanf("%d", &j);
addedge(id(1, i), id(2, j), 1);
}
}
dinic(s, t);
bool flg = 1;
for (int i = lnk[t]; i; i = nxt[i]) {
flg &= !val[i ^ 1];
}
puts(flg ? "Yes" : "No");
return 0;
}