题目大意：有 $k$ 种类型和 $n$ 个题目，每个题目会适应部分类型，第$i$个类型需要$s_i$的题，一道题只能满足一种类型，现要求出满足所有类型的题目的方案
题解：看到匹配，想到网络流，源点向试题连一条容量为$1$的边，试题向每个可以的类型连一条容量为$1$的边，类型向汇点连容量为需要的量的边。跑最大流即可，若最大流小于$\sum\limits_{i=1}^k s_i$则输出无解，否则对于每一个类型找到对它有贡献的题目，输出。
卡点：无
C++ Code：
#include <cstdio>
#include <cstring>
#define maxn 1500
using namespace std;
const int inf = 0x3f3f3f3f;
int k, n, m, p, a;
int s[maxn];
inline int min(int a, int b) {return a < b ? a : b;} int head[maxn], cnt = 2;
struct Edge {
int to, nxt, w;
} e[20 * 1010 << 1];
void add(int a, int b, int c) {
e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt;
e[cnt ^ 1] = (Edge) {a, head[b], 0}; head[b] = cnt ^ 1;
cnt += 2;
} int st, ed;
int d[maxn], q[maxn], h, t;
bool bfs() {
memset(d, 0, sizeof d);
d[q[h = t = 0] = st] = 1;
while (h <= t) {
int u = q[h++];
if (u == ed) return true;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!d[v] && e[i].w) {
d[v] = d[u] + 1;
q[++t] = v;
}
}
}
return d[ed];
}
int dfs(int u, int low) {
if (u == ed || !low) return low;
int v, w, res = 0;
for (int i = head[u]; i; i = e[i].nxt) {
v = e[i].to;
if (d[v] == d[u] + 1 && e[i].w) {
w = dfs(v, min(low - res, e[i].w));
e[i].w -= w;
e[i ^ 1].w += w;
res += w;
if (res == low) return low;
}
}
if (!res) d[u] = -1;
return res;
}
int dinic() {
int ans = 0;
while (bfs()) ans += dfs(st, inf);
return ans;
}
int main() {
scanf("%d%d", &k, &n);
st = 0, ed = k + n + 1;
for (int i = 1; i <= k; i++) {
scanf("%d", &s[i]);
add(i + n, ed, s[i]);
m += s[i];
}
for (int i = 1; i <= n; i++) {
scanf("%d", &p);
add(st, i, 1);
for (int j = 0; j < p; j++) {
scanf("%d", &a);
add(i, a + n, 1);
}
}
// puts("finish1");
int ans = dinic();
if (ans < m) {
puts("No Solution!");
return 0;
}
for (int i = 1; i <= k; i++) {
printf("%d:", i);
for (int j = head[i + n]; j; j = e[j].nxt) {
int v = e[j].to;
if (e[j].w) printf(" %d", v);
}
puts("");
}
return 0;
}