#wv4q17. Scores

时间限制：500 ms       空间限制：16 MiB       标签： 数据结构 并查集 数学 构造 洛谷月赛 2021 

算法难度等级：0       思维难度等级：0       实现难度等级：0

题目描述

小 A 的班上有 $n$ 个学生。最近他们进行了一场考试，共有 $m$ 个学科。第 $i$ 个学生第 $j$ 门学科的得分为整数 $s_{i,j}\ (0\leq s_{i,j}\leq 100)$。

同学们很重视自己在班上的排名，所以他们经常会比较自己和别的同学的分数。如果一个学生 $i$ 至少有一门学科的分数比 $j$ 高，ta 就会觉得自己不比 $j$ 差；相反，如果 ta 每门学科的分数都比 $j$ 低，ta 就会觉得自己被 $j$ 吊打了。

实际上，上述两种情况并不是严格意义上相反的。但是喜好八卦的小 A 打听到了每两个同学之间的分数情况，他惊讶地发现：一个同学 $i$ 要么被 $j$ 吊打，要么不比 $j$ 差。 同时，如果 $i,j$ 被同一个人吊打，或同时吊打同一个人，则他们之间也有一方被另一方吊打。我们用一个矩阵 $a_{i,j}\ (i\neq j)$ 来描述小 A 知道的同学们之间的分数关系：$a_{i,j}=0$ 表示 $i$ 被 $j$ 吊打；$a_{i,j}=1$ 表示 $i$ 不比 $j$ 差。

小 A 想知道这种情况会不会发生，即是否存在这样一张 $n\times m$ 的成绩表 $s$ 满足矩阵 $a$ 所描述的分数关系，从而确定有没有撒谎的同学。如果存在 $s$，请先输出 YES，再任意输出一种符合要求的成绩表；否则输出 NO。

注意：这里所求的 $s$ 所需满足的条件是 $a$ 的限制，而不只是小 A 所发现的性质，因为他发现的性质已经在给出的 $a$ 中体现。

输入格式

本题有多组数据。

第一行一个整数 $t$，表示该测试点编号。
第二行一个整数 $T$，表示数据组数。

对于每组数据：
第一行两个整数 $n,m$。
接下来 $n$ 行，每行 $n$ 个由空格隔开的 0 或 1 描述 $a$。第 $i+1$ 行第 $j$ 个数表示 $a_{i,j}$。

特别的，为了方便读入，规定 $a_{i,i}=0$。但你需要知道它没有任何实际意义。

输出格式

对于每组数据：

如果不存在满足条件的 $s$，输出一行字符串 NO。
否则先输出一行字符串 YES，再输出 $n$ 行，每行 $m$ 个由空格隔开的整数，第 $i+1$ 行第 $j$ 个数表示 $s_{i,j}\ (0\leq s_{i,j}\leq 100)$。

样例输入输出

0
5
5 3
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
2 7
0 1
0 0
5 4
0 1 1 0 1
0 0 0 0 1
0 1 0 0 1
1 1 1 0 1
1 1 1 1 0
3 1
0 1 1
1 0 1
1 1 0
3 2
0 1 0
0 0 1
1 0 0

YES
100 99 97
98 100 99
95 97 100
0 98 100
99 99 99
YES
98 100 94 98 72 53 53
97 99 93 97 71 52 52
YES
90 80 70 60
50 40 30 20
60 50 40 30
100 90 80 70
40 60 80 100
NO
NO

提示

「Special Judge」

本题使用 Special Judge。请认真阅读输出格式，输出格式有误可能导致 UKE 或 WA。

SPJ 首先会判断你的第一行输出是否与答案相同。
如果相同且答案为 \texttt{YES}，则 SPJ 会判断你的输出是否符合所有限制。
如果有解且你输出 \texttt{YES}，但给出方案错误，你将获得该测试点 $50\%$ 的分数。

你需要满足的限制如下：

• $0\leq s_{i,j}\leq 100$。
• 对于任意 $i,j\ (i\neq j)$，若 $a_{i,j}=0$，则对于任意 $k\ (1\leq k\leq m)$，有 $s_{i,k}<s_{j,k}$；若 $a_{i,j}=1$，则存在一个 $k\in [1,m]$，使得 $s_{i,k}>s_{j,k}$。

你需要注意的是，所有输出都应严格符合输出格式。如果你对答案的存在性判断正确，但是输出方案时 $s_{i,j}<0$ 或 $s_{i,j}>100$，SPJ 会判定为 WA，得 $0$ 分，而不是 $50\%\ \times$ 该测试点分数。

「数据范围与约定」

本题共有 6 个测试点。

• Testcase #0（1 point）：是样例。
• Testcase #1（10 points）：$n=1$。
• Testcase #2（10 points）：$m=1$。
• Testcase #3（30 points）：$m=2$。
• Testcase #4（20 points）：$a_{i,j}=1\ (i\neq j)$。
• Testcase #5（29 points）：无特殊限制。

对于 $100\%$ 的数据，$1\leq n,m\leq 100$，$a_{i,j}\in\{0,1\}$，$T=50$（除 Testcase #0）。
对于 $a$ 的限制：若 $a_{i,j}=a_{i,k}=0$，则 $a_{j,k}$ 和 $a_{k,j}$ 中至少有一个为 $0$；若 $a_{i,k}=a_{j,k}=0$，则 $a_{i,j}$ 和 $a_{j,i}$ 中至少有一个为 $0$。
对于所有测试点，时间限制 500ms，空间限制 16MB。