1252. 挑战NPC
题目描述
小N最近在研究 NP 完全问题,小O看小N研究得热火朝天,便给他出了一道这样的题目:
有 \(n\) 个球,用整数 1 到 n 编号。
还有 \(m\) 个筐子,用整数 1 到 m 编号。
每个筐子最多能装3个球。
每个球只能放进特定的筐子中。
具体有 \(e\) 个条件,第 \(i\) 个条件用两个整数 \(v_i\) 和 \(u_i\) 描述,
表示编号为 \(v_i\) 的球可以放进编号为 \(u_i\) 的筐子中。
每个球都必须放进一个筐子中。
如果一个筐子内有不超过 1个球,那么我们称这样的筐子为半空的。
求半空的筐子最多有多少个,以及在最优方案中,每个球分别放在哪个筐子中。
小N看到题目后瞬间没了思路,
站在旁边看热闹的小I嘿嘿一笑:“水题!”。
然后三言两语道出了一个多项式算法。
小N瞬间就惊呆了,
三秒钟后他回过神来一拍桌子:“不对!这个问题显然是 NP 完全问题,你算法肯定有错!”
小I浅笑:“所以,等我领图灵奖吧!”
小O只会出题不会做题,所以找到了你
——请你对这个问题进行探究,并写一个程序解决此题。
输入
第一行,包含1个正整数 \(T\),表示有 \(T\) 组数据。
对于每组数据,第一行包含 3 个正整数 \(n,m,e\),
表示球的个数,筐子的个数和条件的个数。
接下来 \(e\) 行,每行包含2个整数, \(v_i,u_i\),表示编号为的球可以放进编号为 \(u_i\) 的筐子。
输出
对于每组数据,先输出一行,包含一个整数,表示半空的筐子最多有多少个。
然后再输出一行,
包含 \(n\) 个整数 \(p_1,p_2,\cdots,p_n\),
相邻整数之间用空格隔开,表示一种最优解。
其中 \(p_i\) 表示编号为 \(i\) 的球放进了编号为 \(p_i\) 的筐子。
如果有多种最优解,可以输出其中任何一种。
样例一
输入
1
4 3 6
1 1
2 1
2 2
3 2
3 3
4 3
输出
2
1 2 3 3
样例二
见样例数据下载。
数据范围限制
来源
WC2016
信息
- ID
- 1252
- 难度
- (无)
- 分类
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者