题目链接：P2763 试题库问题

题意

一个试题库中有 nnn 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 mmm 道题组成试卷。并要求试卷包含指定类型的试题的试题数量要达标。试设计一个满足要求的组卷算法。每道题选出来以后就只能算作一种类型了。

解析

匹配问题之二，一对多的的匹配问题，建图跑网络流。

每道题目可以看做与题的类型配对，每种类型的题有数目的要求。最终我们要选出题目，于是我们考虑将所有题目作为多源汇流向最终的汇点。

n+k+1n + k + 1n+k+1号：源点
n+1n + 1n+1 ~ n+kn + kn+k：代表题目的类型
111 ~nnn：代表nnn道题目
000号：汇点
1.1.1.每道题有多种类型，但最终选出来只能算作一种类型，那么其贡献流向的汇点流量应该为111。
2.2.2.每个题只能只能算作一个题型， 所以 题型 到有 相应题型的题目 的流量为111。
3.3.3.每种题目类型需要cnt道题，所以与源点连边的流量为cntcntcnt。

最终流到汇点的流量大于等于mmm就是可行的
注意边的数量并不算很小，博主自己估算为500050005000还RE了一发，最终开到100001000010000才过。

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N = 2000, M =  10000;
struct edge{int to,nex,w;
}e[M];
int head[N], n, k, m, tot = 1;void add(int to,int from,int w){e[++ tot].w = w;e[tot].to = to;e[tot].nex = head[from];head[from] = tot;
}int dep[N];
bool bfs()
{for(int i = 0; i <= n + k + 1; i ++) dep[i] = 0;dep[n + k + 1] = 1;queueq;q.push(n + k + 1);while(!q.empty()){int u = q.front(); q.pop();for(int i = head[u]; i; i = e[i].nex){int v = e[i].to;if(e[i].w && !dep[v]){dep[v] = dep[u] + 1;if(v == 0) return true;q.push(v);}}}return dep[0];
}int dfs(int u,int inflow){if(u == 0)return inflow;int outflow = 0;for(int i = head[u]; i; i = e[i].nex){int v = e[i].to;if(e[i].w && dep[v] == dep[u] + 1){int flow = dfs(v, min(e[i].w, inflow));e[i].w -= flow;e[i ^ 1].w += flow;inflow -= flow;outflow += flow;}}if(!outflow) dep[u] = 0;return outflow;
}int main()
{ios::sync_with_stdio(false);cout.tie(NULL);cin >> k >> n;// 设0为汇点for(int i = 1; i <= n; i ++){ // 每道题有多种题目类型，但最终只能算作一种，所以每道题到汇点的流量为1add(0, i, 1);add(i, 0, 0);}for(int i = 1; i <= k; i ++){// 设n + k + 1为源点int cnt;cin >> cnt;m += cnt;add(i + n, n + k + 1, cnt);add(n + k + 1, i + n, 0);//需要cnt个，所以与源点连边的流量为cnt}for(int i = 1; i <= n; i ++){int num, x;cin >> num;while(num --){cin >> x; //每个题只能只能算作一个题型， 所以到每道题的流量为1add(i, n + x, 1);add(n + x, i, 0); }}int ans = 0;while(bfs()){ans += dfs(n + k + 1, 10000);}if(ans < m){cout << "No Solution!\n";return 0;}vector res;for(int i = n + 1; i <= n + k; i ++){res.clear();for(int j = head[i]; j; j = e[j].nex){if(e[j].to <= n && e[j].w == 0) res.push_back(e[j].to);}cout << i - n << ": ";for(int x : res){cout << x << " ";}cout << "\n";}return 0;
}