题目大意：有 $k$ 种类型和 $n$ 个题目，每个题目会适应部分类型，第$i$个类型需要$s_i$的题，一道题只能满足一种类型，现要求出满足所有类型的题目的方案
题解：看到匹配，想到网络流，源点向试题连一条容量为$1$的边，试题向每个可以的类型连一条容量为$1$的边，类型向汇点连容量为需要的量的边。跑最大流即可，若最大流小于$\sum\limits_{i=1}^k s_i$则输出无解，否则对于每一个类型找到对它有贡献的题目，输出。
卡点：无
C++ Code：
#include#include #define maxn 1500using 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;}