[lnsyoj2594/luoguP2763] 试题库问题

题意

假设一个试题库中有 \(n\) 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性，但在试卷中只计一种。从题库中抽取 \(m\) 道题组成试卷，使试卷包含第 \(i\) 种试题 \(a_i\) 道，共需 \(k\) 道。

sol

建立二分图模型，使左侧点对应试题，右侧点对应类别。
每一个左侧点向对应类别的右侧点连一条容量为 \(1\) 的边，超级源点 \(S\) 向每一个左侧点连一条容量为 \(1\) 的边，每一个右侧点向超级汇点 \(T\) 连一条容量为 \(a_i\) 的边。跑最大流，当且仅当最大流 \(|f|=k\) 时有合法方案。
输出方案时，枚举每一条边即可。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N = 1055, M = 44005, INF = 0x3f3f3f3f;

int h[N], e[M], f[M], ne[M], idx;
int d[N], cur[N];
int n, S, T;
int k, p, m;
vector<int> typ[N], ans[25];

void add(int a, int b, int c) {
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}

void build() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &k, &p);
    n = k + p + 2, S = n - 1, T = n;
    for (int i = 1; i <= p; i ++ ) add(S, i, 1);
    for (int i = 1; i <= k; i ++ ) {
        int t;
        scanf("%d", &t);
        m += t;
        add(p + i, T, t);
    }
    for (int i = 1; i <= p; i ++ ) {
        int t, tp;
        scanf("%d", &t);
        for (int j = 1; j <= t; j ++ ) {
            scanf("%d", &tp);
            add(i, p + tp, 1);
            typ[i].push_back(tp);
        }
    }
}

bool bfs() {
    queue<int> q;
    memset(d, -1, sizeof d);
    d[S] = 0, cur[S] = h[S], q.push(S);
    while (!q.empty()) {
        int t = q.front(); q.pop();
        for (int i = h[t]; ~i; i = ne[i]){
            int j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if (j == T) return true;
                q.push(j);
            }
        }
    }
    return false;
}

int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
        cur[u] = i;
        int j = e[i];
        if (d[j] == d[u] + 1 && f[i]) {
            int t = find(j, min(limit - flow, f[i]));
            if (!t) d[j] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }

    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) while (flow = find(S, INF)) res += flow;
    return res;
}

void print(int res) {
    if (res != m) puts("No Solution!");
    else {
        for (int i = (p + k) * 2 + 1, u = 1; u <= n; u ++ )
            for (int x : typ[u]) {
                if (f[i]) ans[x].push_back(u);
                i += 2;
            }
        
        for (int i = 1; i <= k; i ++ ) {
            printf("%d: ", i);
            for (int x : ans[i]) printf("%d ", x);
            puts("");
        }
    }
}

int main(){
    build();

    int res = dinic();

    print(res);
}