Description

未名湖附近共有N个大小湖泊L1, L2, …, Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙\(Fi(1 ≤ i ≤ N)\)。如果湖泊Li和Lj之间有水路相连,则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, …, xn,请你给出每两个湖泊之间的相连关系。

Input

第一行是测试数据的组数\(T(0 ≤ T ≤ 20)\)。每组数据包括两行,第一行是整数N(2 < N < 10),第二行是N个整数,\(x1, x2,…, xn(0 ≤ xi ≤ N)\)。

Output

对输入的每组测试数据,如果不存在可能的相连关系,输出”NO”。否则输出”YES”,并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

Sample Input

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

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
YES
0 1 0 1 1 0 1
1 0 0 1 1 0 0
0 0 0 1 0 0 0
1 1 1 0 1 1 0
1 1 0 1 0 1 0
0 0 0 1 1 0 0
1 0 0 0 0 0 0

NO

YES
0 1 0 0 1 0
1 0 0 1 1 0
0 0 0 0 0 1
0 1 0 0 0 0
1 1 0 0 0 0
0 0 1 0 0 0

Thoughts

给一个无向图的度序列判定是否可图化,并求方案。

  • 可图化的判定:\(d1+d2+……dn=0(mod 2)\)。关于具体图的构造,我们可以简单地把奇数度的点配对,剩下的全部搞成自环。
  • 可简单图化的判定 (Havel定理) :把序列排成不增序,即\(d1>=d2>=……>=dn\),则d可简单图化当且仅当\(d’={d_2-1,d_3-1,……d_{d1+1}-1, d_{d1+2},d_{d1+3},……dn}\)可简单图化。简单的说,把\(d\)排序后,找出度最大的点(设度为\(d_1\)),把它与度次大的\(d_1\)个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct Frog {
int pos, deg;
bool operator < (const Frog & F) const {
return deg > F.deg;
}
} frog[11];

int n, e[11][11];

bool Havel() {
for(int i = 0; i < n; ++i) {
sort(frog + i, frog + n);
for(int j = 1; j <= frog[i].deg; ++j) {
if(i + j >= n || frog[i + j].deg == 0) {
return false;
} else {
--frog[i + j].deg;
e[frog[i].pos][frog[i + j].pos] = 1;
e[frog[i + j].pos][frog[i].pos] = 1;
}
}

}
return true;
}

int main() {
int t; scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &frog[i].deg);
frog[i].pos = i;
}
memset(e, 0, sizeof(e));
if(Havel()) {
puts("YES");
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
printf("%d%c", e[i][j], " \n"[j == n - 1]);
}
}
} else {
puts("NO");
}
putchar('\n');
}
return 0;
}

Record

  • 2018年08月18日 完成题解