题目描述
假设一个试题库中有 n 道试题。
每道试题都标明了所属类别。
同一道题可能有多个类别属性。
现要从题库中抽取 m 道题组成试卷。
并要求试卷包含指定类型的试题。
试设计一个满足要求的组卷算法。
输入格式
第 1 行有 2 个正整数 k 和 n,k 表示题库中试题类型总数,n 表示题库中试题总数。
第 2 行有 k 个整数,第 i 个整数表示要选出的类型 i 的题数(可能为 0)。
这 k 个数相加就是要选出的总题数 m。
接下来的 n 行给出了题库中每个试题的类型信息。
每行的第 1 个正整数 p 表明该题可以属于 p 类,接着的 p 个数是该题所属的类型号。
类别编号和题号都从 1 开始。
输出格式
第 i 行输出 i: 后接类型 i 的题号。
如果有多个满足要求的方案,只要输出 1 个方案。
如果问题无解,则输出 No Solution!。
拆点+最大流
建图时:
(1)从 源点 向每个类别所代表的点(编号为1~k)连一条边,边的容量为该类别需要的试题数;
(2)每个试题所代表的点应该拆为入点(编号k+1~k+n)和出点(编号k+n+1~k+2*n),并从入点向出点连一条容量为1的边,因为每个试题只能被使用一次;
(3)从 每个类别所代表的点 向 可以用作此类别的试题所代表的点的入点 连一条边,容量为1;
(4)从 每个试题所代表的点的出点 向 汇点 连一条边,容量随意
这样建图后,就跑一遍最大流,如果最大流小于m,说明有些类别没有拿到足够的试题,因此无解;
否则,遍历每个类别所代表的点的出边的剩余容量,若为0,说明该出边对应的试题被选为了这个类别
C++ 代码
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>edges[3010];
int n,k,idx=-1,depth[3010],cur[3010],f[30010];
int S,T;
void add(int a,int b,int c){
edges[a].push_back({b,++idx}),f[idx]=c;
edges[b].push_back({a,++idx}),f[idx]=0;
}
bool bfs(){
queue<int>nodes;
nodes.push(S);
memset(depth,-1,sizeof depth);
depth[S]=cur[S]=0;
while(!nodes.empty()){
int temp=nodes.front();
nodes.pop();
for(int i=0;i<edges[temp].size();i++){
int t=edges[temp][i].first,e=edges[temp][i].second;
if(f[e]==0||depth[t]!=-1) continue;
cur[t]=0;
depth[t]=depth[temp]+1;
if(t==T) return true;
nodes.push(t);
}
}
return false;
}
int dfs(int now,int limit){
if(now==T) return limit;
int flow=0;
for(int i=cur[now];i<edges[now].size()&&flow<limit;i++){
int t=edges[now][i].first,e=edges[now][i].second;
cur[now]=i;
if(f[e]==0||depth[t]!=depth[now]+1) continue;
int u=dfs(t,min(f[e],limit-flow));
if(u==0) depth[t]=-1;
flow+=u,f[e]-=u,f[e^1]+=u;
}
return flow;
}
int dinic(){
int res=0;
while(bfs()){
res+=dfs(S,0x3f3f3f3f);
}
return res;
}
int main(){
cin>>k>>n;
S=0,T=3005;
int m=0;
for(int i=1,a;i<=k;i++){
cin>>a;
m+=a;
add(S,i,a);
}
for(int i=1,a,b;i<=n;i++){
cin>>a;
for(int t=1;t<=a;t++){
cin>>b;
add(b,i+k,1);
}
add(i+k,i+n+k,1);
add(i+n+k,T,1);
}
int flow=dinic();
if(flow<m){
cout<<"No Solution!";
return 0;
}
else{
for(int i=1;i<=k;i++){
cout<<i<<": ";
for(int t=0;t<edges[i].size();t++){
int x=edges[i][t].first,y=edges[i][t].second;
if(f[y]==0&&x!=S) cout<<x-k<<" ";
}
cout<<endl;
}
}
return 0;
}
这道题可以不用拆点,观察建图方法:
1
到n
)n+1
到n+k
)所有容量都设为
1
,每道题只会被选择一次。