前言

总结了一种新的网络最大流的方法。

题目大意

假设一个试题库中有 $n$ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。
$2\leq k \leq 20$，$k \leq n \leq 10^3$。

思路

首先可以发现网络流的思路，肯定是最大流。然后本题应该是没有给定的源点和汇点的，所以采用超级源/汇点（为了方便这里做一下总结，所有的超级汇点之后都做成 0，超级源点为 MAXN-1）。之后考虑填边和点。大多数题解中采用的是先放试题，但是我觉得从类别去匹配题目可能会更清晰一点。首先肯定要从源点向每一个类型建一条边权为需要的题目数的边。因为需要这么多的水流过去。

然后第一直觉是直接跟有这个类型的题目连一条边权为 $1$ 的边，之后在把所有题目与超级汇点连一条边长为 $1$ 的边，再跑一遍最大流记录路径就行了。

代码

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
typedef long long ll;
const ll MAXN = 6e3 + 5;
const ll MAXM = 6e3 + 5;
const ll INF = ll(1e30);

ll k, n, s = 5e3 + 1, t = 5e3 + 2;
struct edge {
    ll to, weight, nxt;
} e[MAXM * 2];
ll head[MAXN], tot = 1;

void add(ll u, ll v, ll w) {
    e[++tot].nxt = head[u];
    e[tot].to = v;
    e[tot].weight = w;
    head[u] = tot;
}

bool inq[MAXN];
struct node {
    ll last, edge;
} pre[MAXN];

bool bfs() {
    memset(inq, false, sizeof(inq));
    queue<ll> q;
    inq[s] = true;
    q.push(s);

    while (!q.empty()) {
        ll u = q.front();
        q.pop();

        for (ll i = head[u]; i; i = e[i].nxt) {
            ll v = e[i].to, w = e[i].weight;

            if (!inq[v] && w != 0) {
                pre[v].last = u;
                pre[v].edge = i;

                if (v == t) {
                    return true;
                }

                inq[v] = true;
                q.push(v);
            }
        }
    }

    return false;
}

ll ans[MAXN][300];
ll place[MAXN];
ll m,nm;
ll ek() {
    ll flow = 0;

    while (bfs()) {
        ll Min = INF;

        for (ll i = t; i != s; i = pre[i].last) {
            Min = min(Min, e[pre[i].edge].weight);
        }

        flow += Min;
        ll last = 0;

        for (ll i = t; i != s; i = pre[i].last) {
            if (pre[i].last != s) {
                last = pre[i].last;
            }
        }

        ans[last][++place[last]] = pre[t].last;
        nm++;
        if(nm==m){
            break;
        }
        for (ll i = t; i != s; i = pre[i].last) {
            e[pre[i].edge].weight -= Min;
            e[pre[i].edge ^ 1].weight += Min;
        }
    }

    return flow;
}

int main() {
    scanf("%lld%lld", &k, &n);

    for (int i = 1; i <= k; ++i) {
        ll a;
        scanf("%lld", &a);
        add(s, i, a);
        add(i, s, 0);
        m += a;
    }

    for (int i = 1; i <= n; ++i) {
        add(i + n, t, 1);
        add(t, i + n, 0);
    }

    for (int i = 1; i <= n; ++i) {
        ll p, a;
        scanf("%lld", &p);

        for (int j = 1; j <= p; ++j) {
            scanf("%lld", &a);
            add(a, i + n, 1);
            add(i + n, a, 0);
        }
    }

    if (ek() == m) {
        for (int i = 1; i <= k; ++i) {
            printf("%d: ", i);

            for (int j = 1; j <= place[i]; ++j) {
                printf("%lld ", ans[i][j] - n);
            }

            printf("\n");
        }
    } else {
        printf("No Solution!\n");
    }

    return 0;
}

延伸

本题是一个题目可以用于多个类型。可如果本题一道题只能选择一个类型生效该怎么做呢？我们可以在本题做法的基础上在加一个假点作为阀门，之后把类型连到假点上，这样假点最多只能流一个到题目了。这就是阀门优化（瞎起的名）。

总结

记录了原题的做法同时也对一个延伸的题目做出了一个阀门优化的思路。