UOJ Logo Universal Online Judge

UOJ

#171. 【WC2016】挑战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$,表示编号为 $v_i$ 的球可以放进编号为 $u_i$ 的筐子。

输出格式

对于每组数据,先输出一行,包含一个整数,表示半空的筐子最多有多少个。

然后再输出一行,包含 $n$ 个整数 $p_1, p_2, \dots , p_n$,相邻整数之间用空格隔开,表示一种最优解。其中 $p_i$ 表示编号为 $i$ 的球放进了编号为 $p_i$ 的筐子。如果有多种最优解,可以输出其中任何一种。

样例一

input

1
4 3 6
1 1
2 1
2 2
3 2
3 3
4 3

output

2
1 2 3 3

样例二

见样例数据下载。

限制与约定

对于所有数据,$T \leq 5$,$1 \leq n \leq 3m$。保证 $1 \leq v_i \leq n, 1 \leq u_i \leq m$,且不会出现重复的条件。

保证至少有一种合法方案,使得每个球都放进了筐子,且每个筐子内球的个数不超过 $3$。

各测试点满足以下约定:

测试点编号 $m$ 约定
1$\leq 10$$n \leq 20$,$e \leq 25$
2
3$\leq 100$$e = nm$
4存在方案使得有 $m$ 个半空的筐子
5不存在有半空的筐子的方案
6
7
8
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载