poj1659(Havel-Hakimi定律)
Time Limit: 5000MS | Memory Limit: 10000K | |||
Total Submissions: 6676 | Accepted: 2904 | Special Judge |
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
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
Source
定理1.2(Havel-Hakimi定理) 由非负整数组成的非增序列s:d1, d2, …, dn(n ≥2, d1 ≥1)是可图的,当且仅当序列
s1: d2
– 1, d3
– 1, …, dd1+1
– 1, dd1+2
, …, dn
是可图的。序列s1中有n-1个非负整数,s序列中d1后的前d1个度数(即d2~dd1+1)减1后构成
s1中的前d1个数。
本题的意思实际上是给定一个非负整数序列,问是不是一个可图的序列,也就是说能不能根
据这个序列构造一个图。这需要根据Havel-Hakimi定理(定理1.2)中的方法来构图,并在构图
中判断是否出现了不合理的情形。有以下两种不合理的情形:
(1) 某次对剩下序列排序后,最大的度数(设为d1)超过了剩下的顶点数;
(2) 对最大度数后面的d1个度数各减1后,出现了负数。
一旦出现了以上两种情形之一,即可判定该序列不是可图的。
如果一个序列是可图的,本题还要求输出构造得到的图的邻接矩阵,实现思路是:
(1) 为了确保顶点序号与输入时的度数顺序一致,特意声明了一个vertex结构体,包含了顶点
的度和序号两个成员。
(2) 每次对剩下的顶点按度数从大到小的顺序排序后,设最前面的顶点(即当前度数最大的顶
点)序号为i、度数为d1,对后面d1个顶点每个顶点(序号设为j)度数减1,并连边,即在邻接
矩阵Edge中设置Edge[i][j]和Edge[j][i]为1。
#include <stdio.h> #include <math.h> #include<algorithm> #include<cstring> #include<stdlib.h> #define N 15 struct vertex { int degree; int index; }; vertex VE[N]; int edge[N][N]; int cmp(const void *a,const void *b) { return ((vertex*)b)->degree-((vertex*)a)->degree; } int main() { freopen("input.txt","r",stdin); int n,T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&VE[i].degree); VE[i].index=i; } int flag=1; memset(edge,0,sizeof(edge)); for(int i=1;i<=n&&flag;i++) { qsort(VE+i,n-i+1,sizeof(VE[0]),cmp); int d1=VE[i].degree; int f=VE[i].index; if(d1>n-i)flag=0; for(int j=1;j<=d1&&flag;j++) { int t=VE[i+j].index; if(VE[i+j].degree<=0)flag=0; VE[i+j].degree--; edge[f][t]=edge[t][f]=1; } } if(flag) { puts("YES"); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",edge[i][j],j==n?'\n':' '); } else { puts("NO"); } puts(""); } return 0; }