洛谷P2763 试题库问题题解

题意：

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。

现要从题库中抽取 $m$ 道题组成试卷。

并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

注意，同一道题可能有多个类别属性，但是每道题在组卷时只能归类于一种类型。

对于给定的组卷要求，计算满足要求的组卷方案。

输入格式：

第一行有两个正整数 $k$ 和 $n$。$k$ 表示题库中试题类型总数，$n$ 表示题库中试题总数。

第二行有 $k$ 个正整数，第 $i$ 个正整数表示要选出的类型 $i$ 的题数。这 $k$ 个数相加就是要选出的总题数 $m$。

接下来的 $n$ 行给出了题库中每个试题的类型信息。每行的第一个正整数 $p$ 表明该题可以属于 $p$ 类，接着的 $p$ 个数是该题所属的类型号。

输出格式:

输出共 $k$ 行，第 $i$ 行输出 i: 后接类型 $i$ 的题号。

如果有多个满足要求的方案，只要输出一个方案。

如果问题无解，则输出No Solution!。

数据范围：

$2\leq k \leq 20$，$k \leq n \leq 10^3$。

网络最大流基础题。

源点 $s$ 向每道题连边，流量为 $1$ 。

每道题向对应的类型连边，流量为 $1$ 。可以把题目的点当作“左部点”。

每种类型向汇点 $t$ 连边，流量为该类型所需要的题数。把类型当作“右部点”。

跑了最大流之后，如果类型向 $t$ 的边满流，则存在合法解。

输出方案只需要遍历“右部点”的出边即可（其实就是“左部点”的反向边）

理论时间复杂度 $\mathcal{O}(n^3k)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

int n,m,k,s,t,tot,pos=1,now[N * 2],head[N * 2],dep[N * 2];
struct Edge { int u,v,w,next; } e[N * 22 * 2];
void addEdge(int u,int v,int w)
{ e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
void add(int u,int v,int w) { addEdge(u,v,w); addEdge(v,u,0); }
queue<int> q;
bool bfs()
{
    for(int i=1; i<=tot; i++) dep[i] = INF;
    dep[s] = 1; now[s] = head[s]; q.push(s);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            if(e[i].w > 0 && dep[v] == INF)
            {
                dep[v] = dep[u] + 1;
                now[v] = head[v]; q.push(v);
            }
        }
    }
    return dep[t] != INF;
}
int dfs(int u, int in)
{
    if(u == t) return in;
    int out = 0;
    for(int i = now[u]; i; i = e[i].next)
    {
        if(!in) break; int v = e[i].v; now[u] = i;
        if(e[i].w > 0 && dep[v] == dep[u] + 1)
        {
            int res = dfs(v, min(in, e[i].w));
            e[i].w -= res; e[i ^ 1].w += res;
            in -= res; out += res;
        }
    }
    if(!out) dep[u] = INF;
    return out;
}
int Dinic()
{
    int res = 0;
    while(bfs()) res += dfs(s,INF);
    return res;
}
void print(int u)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(e[i].w > 0 && v <= n) cout << ' ' << v;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);

    cin >> k >> n; s = n + k + 1; tot = t = s + 1;
    for(int i=1,x; i<=k; i++)
    { cin >> x; m += x; add(n + i, t, x); } // B -> t
    for(int i=1,x,y; i<=n; i++)
    {
        cin >> x; add(s,i,1); // s -> A
        for(int j=1; j<=x; j++)
        { cin >> y; add(i, n + y, 1); } // A -> B
    }
    if(Dinic() == m)
    {
        for(int i=1; i<=k; i++)
        { cout << i << ':'; print(n + i); cout << '\n'; }
        return 0;
    }
    cout << "No Solution!\n";
    return 0;
}