洛谷 P2763 试题库问题

传送门 $\looparrowright$

题目描述

问题描述

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

编程任务

对于给定的组卷要求，计算满足要求的组卷方案。

输入格式

第一行有两个正整数 $k$ 和 $n$。$k$ 表示题库中试题类型总数，$n$ 表示题库中试题总数。
第二行有 $k$ 个正整数，第 $i$ 个正整数表示要选出的类型 $i$ 的题数。这 $k$ 个数相加就是要选出的总题数 $m$。
接下来的 $n$ 行给出了题库中每个试题的类型信息。每行的第一个正整数 $p$ 表明该题可以属于 $p$ 类，接着的 $p$ 个数是该题所属的类型号。

输出格式

输出共 $k$ 行，第 $i$ 行输出 i: 后接类型 $i$ 的题号。
如果有多个满足要求的方案，只要输出一个方案。
如果问题无解，则输出No Solution!。

输入输出样例

输入 #1

3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3

输出 #1

1: 1 6 8
2: 7 9 10
3: 2 3 4 5

说明/提示

$2\leqslant k \leqslant 20$，$k \leqslant n \leqslant 10^3$。

分析

首先要明确一下题意，题目描述有一些不严谨。事实上，每道题虽可以属于多个类型，但却只能与一种类型相匹配，即最后输出时不能在不同种类型中出现同一道题。
每个类型之间和每道题目直接都不会有内在联系，此题要求进行类型与题目的匹配：要求一个类型有多个题目，可以建立二分图多重匹配模型。首先规定节点编号，编号为 $1\sim n$ 的节点表示题目，编号为 $n+1\sim n+k$ 的节点表示类型。若题目 $i$ 属于类型 $j$，则建立一条 $i$ 到 $j+n$ 的边。
网络流是解决二分图最常用也是较为高效的方法。设超级源点 $s$，编号为 $0$；超级汇点 $t$，编号为 $n+k+1$。接下来考虑如何设置各条边的容量，其核心是：通过设置容量来保证网络流量具有实际意义。令 $s$ 向 $1\sim n$ 的节点连边，容量为 $1$，题目节点和类型节点之间的边容量也设置为 $1$，这就意味着一道题目至多只会被使用一次。接着令 $n+1\sim n+k$ 的节点向 $t$ 连边，容量为各个类型需要的题目数量；这就意味着网络最大流一定不超过 $m$，并且，当最大流达到 $m$ 时，流入 $n+1\sim n+k$ 中任意节点的流量就等于该点表示的类型需要的题目数量。
建图完成后，用 $\text{Dinic}$ 算法计算出最大流 $\mathrm{maxflow}$，若 $\text{maxflow}=m$，则存在匹配方案；否则，不存在。当存在匹配方案时，需要考虑匹配方案如何输出。我们注意到，$\text{Dinic}$ 算法建边时，会相应建立一条反向边，在残量网络上增广时，反向边的容量会被改变；反向边容量初始为 $0$，若反向边容量不为零，说明其对应的正向边对最大流有贡献。因此，不妨枚举由类型节点流向题目节点的反向边，若反向边指向一个题目节点，且其上的流量不为零，说明该题目与该类型匹配。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P2763
Date: 7/25/2020 
Description: Maximum Flow
*******************************************************************/
#include<cstring>
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int N=1006;
const int inf=0x3f3f3f3f;
struct E
{
	int to;
	int cap;
	int Next;
}edge[N*N<<1];
int head[N],tot;
int s,t;//源点 汇点
int depth[N];//节点层次
int n,k,m;
void init();
inline void add_edge(int,int,int);
bool bfs();
int dfs(int x,int flow);
int Dinic();
int main()
{
	cin>>k>>n;
	init();
	int i,j;
	for(i=1;i<=k;i++)
	{
		int num;//每种类型的要求数量
		scanf("%d",&num);
		m+=num;
		add_edge(n+i,t,num);
	}
	for(i=1;i<=n;i++)
	{
		int p;
		scanf("%d",&p);
		while(p--)
		{
			int type;
			scanf("%d",&type);
			add_edge(i,type+n,1);
		}
	}
	for(i=1;i<=n;i++) add_edge(s,i,1);
	if(Dinic()==m)
	{
		//枚举类型
		for(i=1;i<=k;i++)
		{
			printf("%d: ",i);
			//访问类型指向题目的边
			for(j=head[i+n];~j;j=edge[j].Next)
			{
				if(edge[j].to>n||edge[j].to==s) continue;
				if(edge[j].cap) printf("%d ",edge[j].to);
			}
			putchar('\n');
		}
	}
	else puts("No Solution!");
	return 0;
}
void init()
{
	tot=1;
	s=0;
	t=n+k+1;
	memset(head,-1,sizeof(head));
}
inline void add_edge(int u,int v,int cap)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].Next=head[u];
	head[u]=tot;
	//建立反边
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool bfs()
{
	memset(depth,0,sizeof(depth));
	queue<int>q;
	q.push(s);
	depth[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			//残量网络上构建分层图
			if(edge[i].cap&&!depth[y])
			{
				q.push(y);
				depth[y]=depth[x]+1;
				if(y==t) return 1;//汇点可达
			}
		}
	}
	return 0;
}
int dfs(int x,int flow)//当前节点 当前流量
{
	//dfs 返回残量网络上可增广的流量
	if(x==t) return flow;
	int rest=flow;//rest 剩余流量
	int temp;
	for(register int i=head[x];~i&&rest;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(edge[i].cap&&depth[y]==depth[x]+1)
		{
			temp=dfs(y,min(rest,edge[i].cap));
			if(!temp) depth[y]=0;//剪枝 去掉增广完毕的点
			edge[i].cap-=temp;
			edge[i^1].cap+=temp;
			rest-=temp;
		}
	}
	return flow-rest;
}
int Dinic()
{
	int maxflow=0;
	while(bfs()) maxflow+=dfs(s,inf);
	return maxflow;
}