「Luogu 2763」试题库问题

发表于 | | 阅读次数:
字数统计: 785 字

Description

题目链接：Luogu 2763

假设一个试题库中有 $n$ 道试题，试题被分为 $k$ 个类型。每道试题都标明了所属类别，同一道题可能有多个类别属性。现要从题库中抽取 $m$ 道题组成试卷，每道题只能被选择一次。给出每个类型需要的题数，试设计一个满足要求的组卷方案。

数据范围：$2\le k\le 20$，$k\le n\le 1000$

Solution

由于这道题是关于匹配的问题，所以我们可以考虑用网络流解决。

首先建立源点 $s$ 和汇点 $t$。

  • 源点和试题相连。因为一道题只能被选择一次，所以容量为 $1$。
  • 汇点与类型相连。因为每个类型需要若干道题目，所以容量为“这个类型需要的题目数量”。
  • 每道试题和它所属的类型相连。因为每道题只能满足一个类型，所以容量为 $1$。

接下来直接跑最大流就行了。

最后分析一下如何判断是否有解。如果最大流小于 $m$，那么显然无解，否则就是有解。输出方案时，我们对于每个类型 $i$，如果它向试题的连边（显然这条边应该是反向边）的残量不为 $0$，那么表示这条边的正向边是满流的，也就是选择了这个匹配，就可以输出方案了。

时间复杂度：$O(n^2m)$（$\text{Dinic}$）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=2e3+5,M=1e5+5;
const int INF=1<<30;
int n,k,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
    add(u,v,w),add(v,u,0);
}
bool bfs(int s,int t) {
    memset(dep,0,sizeof(dep));
    memcpy(cnr,lnk,sizeof(lnk));
    std::queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
        }
    }
    return dep[t];
}
int dfs(int u,int t,int flow) {
    if(u==t) return flow;
    int ans=0;
    for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
        cnr[u]=i;
        int v=ter[i];
        if(val[i]&&dep[v]==dep[u]+1) {
            int x=dfs(v,t,std::min(val[i],flow-ans));
            if(x) val[i]-=x,val[i^1]+=x,ans+=x;
        }
    }
    if(ans<flow) dep[u]=-1;
    return ans;
}
int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t)) {
        int x;
        while((x=dfs(s,t,INF))) ans+=x;
    }
    return ans;
}
int main() {
    scanf("%d%d",&k,&n);
    int sum=0;
    int s=0,t=k+n+1;
    for(int i=1;i<=k;++i) {
        int x;
        scanf("%d",&x),sum+=x;
        addedge(n+i,t,x);
    }
    for(int i=1;i<=n;++i) {
        int m;
        scanf("%d",&m);
        while(m--) {
            int x;
            scanf("%d",&x);
            addedge(i,n+x,1);
        }
        addedge(s,i,1);
    }
    if(dinic(s,t)!=sum) return puts("No Solution!"),0;
    for(int u=1;u<=k;++u,puts("")) {
        printf("%d:",u);
        for(int i=lnk[n+u];i;i=nxt[i]) {
            if(ter[i]!=t&&val[i]) printf(" %d",ter[i]);
        }
    }
    return 0;
}
0%