未名湖附近共有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
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
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
题意:
给出每个青蛙的邻居的个数,判断是否存在相连关系。
思路:
判断是否可以构成图。
给定一个非负整数序列{dn},若存在一个无向图使得图中各点的度与此一一对应,则称此序列可图化。判断一个序列是否可图化,用Havel-Hakimi定理(握手定理)判断。
(1)先从小到大排序
(2) 删去最后一个数字,并且把对后一个数字对应个数的元素减一
(3)继续排序,进行上述操作,直至所有元素都为0,就表明序列可图化,如果出现元素为负或者大于元素个数就可以判断为不能构成图。
举例:
序列:4 3 1 5 4 2 1
排序之后:1 1 2 3 4 4 5
删除5对前面5个数减1操作
1 0 1 2 3 3
排序
0 1 1 2 3 3
删除3对前面3个数减1操作
0 1 0 1 2
排序
0 0 1 1 2
删除2 对前面2个数减1操作
0 0 0 0
全为0,可图
写完发现答案跟样例答案不一样但是,才发现是special judge!
代码:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct data
{
int h;
int mark;
};
int cmp(data x,data y)
{
return x.h<y.h;
}
int main()
{
int n,t,i,flag,m,j;
data a[25];
int map[25][25];
scanf("%d",&t);
while(t--)
{
memset(map,0,sizeof(map));
flag=0;
scanf("%d",&n);
m=n;
for(i=0;i<n;i++)
{
scanf("%d",&a[i].h);
a[i].mark=i;
}
while(n)
{
sort(a,a+n,cmp);
if(a[n-1].h<0||a[n-1].h>=n)
{
flag=1;
break;
}
for(i=n-2;i>n-2-a[n-1].h;i--)
{
map[a[n-1].mark][a[i].mark]=map[a[i].mark][a[n-1].mark] = 1;
a[i].h--;
}
n--;
}
if(flag==1)
printf("NO\n");
else
{
printf("YES\n");
for(i=0;i<m;i++)
{
for(j=0;j<m;j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
}
printf("\n");
}
return 0;
}