P2763 试题库问题

从单位匹配到带配额的二分图分配

问题

P2763 试题库问题
有 $n$ 道题，每题可归入若干类别；第 $i$ 类必须恰好选 $k_i$ 道题，任意一道题至多被选一次。要求判断能否满足全部配额，并输出一份分配。

数据规模：$2\le k\le20$，$k\le n\le10^3$，类别配额总和即所需选题数。

在 P2756 飞行员配对方案问题 中，左右两侧每个点都只能使用一次，因此对应的源汇边容量都是 $1$。本题仍然存在“类别—题目”的二分关系，区别只是一个类别不再只需要匹配一道题，而是需要取得 $k_i$ 道题。

于是建立 $S \to$类别 $\to$ 题目 $\to T$ 的网络，源点到第 $i$ 个类别的容量设为 $k_{i}$，类别到允许选择的题目容量设为 $1$，每道题到汇点的容量也设为 $1$。

类别侧容量 $k_i$ 表达需要填充的配额，题目侧容量 $1$ 保证一道题至多被使用一次，中间边则只负责表达类别与题目的兼容关系。也就是说，本题在 P2756 的基本匹配结构基础上，只是把左侧的单位容量推广成了配额。

可行性

如何判断当前的分配方案是否合法？

设所有类别的总需求为 need，那么源点发出的总容量就是 need，若最大流达到 need，则所有 $S\to$ 类别边必然全部饱和，于是每类恰好取得 $k_i$ 道题。

如果最大流小于 need，说明无论如何重新调整分配，都至少存在一个类别无法填满配额，因此本题实际上是在用最大流完成一个 可行性判定。

最大流结束后，只检查“类别 $\to$ 题目”的原始正向边；若其初始容量为 $1$、最终残量为 $0$，就说明这条关系实际承载了 $1$ 单位流，对应题目被分配给该类别。

▶

P2763 建图与方案恢复

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

void solve( ) {
    int k = read( ), n = read( );

    int S = 0, T = n + k + 1;
    init( T );

    ll need = 0;
    for( int i = 1; i <= k; ++ i ) {
        int ki = read( );
        need += ki;
        add_edge( S, n + i, ki );
    }

    for( int i = 1; i <= n; ++ i ) {
        int p = read( );
        for( int j = 1; j <= p; ++ j ) {
            int u = read( );
            add_edge( n + u, i, 1 );
        }
        add_edge( i, T, 1 );
    }

    ll mxflow = Dinic( S, T, T );

    if( mxflow != need ) {
        cout << "No Solution!" << '\n';
        return;
    }
    // printf( "%lld\n", mxflow );

    for( int i = 1; i <= k; ++ i ) {
        cout << i << ": ";
        int u = n + i;
        for( int id : adj[u] ) {
            auto [v, c] = edge[id];
            if( 1 <= v && v <= n && c == 0 ) {
                cout << v << " ";
            }
        }
        cout << '\n';
    }
}

复盘

最大流本身只表示最多能够完成多少次分配，因此必须与总需求 need 比较，从而判定合法性。