Frogs’ Neighborhood
Time Limit: 5000MS   Memory Limit: 10000K
Total Submissions: 9897   Accepted: 4137   Special Judge

Description

There are N lakes around Weiming Lake L1, L2… Ln(which includes Weiming Lake), each lake Li has a frog Fi(1 ≤ I ≤ N). If lakes Li and Lj are connected by water, frogs Fi and Fj are called neighbors to each other. Now we know the number of neighbors per frog x1, X2… Xn, please give the relationship between each two lakes.

Input

The first line is the number of groups of test data T(0 ≤ T ≤ 20). Each group of data contains two rows, the first row is the integer N(2 < N < 10), and the second row is the integer N, x1, x2… , xn(0 ≤ xi ≤ N).

Output

Output “NO” for each set of input test data if NO possible connection exists. Otherwise, “YES” is output and the N×N matrix is used to represent the adjacent relationship between lakes, that is, if there is a waterway connection between lake I and lake J, the JTH digit in line I is 1, otherwise it is 0. Print a space between two digits. If there are multiple possibilities, you just have to give one case that works. Output a blank line between two adjacent sets of test data.

Sample Input

3. 1Copy the code

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 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0Copy the code

Source

POJ or – 2004.05.15 Alcyone @ pku

Title link: poj.org/problem?id=1659

Given a sequence of non-negative integers, ask if the sequence is graphable and if it is graphable, and then plot it according to the Havel-Hakimi theorem

Answer:

 

Havel — Hakimi theorem: a non-increasing sequence s:d1, d2, dn (n>=2, d1>=1) composed of non-negative numbers is graphable, if only the sequence

 

S1: D2-1, D3-1,dd1+ 1-1, DD1 +2, dn

 

It’s graphable. There are n-1 non-negative numbers in s1, and the first d1 degree after D1 in S is subtracted by 1 to form the first D1 number in S1.

 

**** Determination process: (1) Sort the current sequence so that it is decreasing

 

(2) Start from v [2] and match the following v [1] digits -1

 

(3) Continue to loop until the current sequence is negative (that is, not graphable) or the current sequence is all 0 (graphable) exit.

3. For example, delete the first item 7 of sequence S and subtract 1 from each of the subsequent 7 items to get: 6,3,2,2,2,1,0. Continue to delete the first item 6 of sequence and subtract 1 from each of the subsequent 6 items to get: 2,1,1,1,0, minus 1, negative numbers at this point, so the sequence is not graphable

4 3 1 5 4 2 1 3 3 2 1 1 0 delete 3 Subtract 1 from the last 5 digits 3 3 2 1 0 1 Sort 3 3 2 1 1 0 delete 3 Subtract 1 from the last 3 digits 2 1 0 1 0 sort 2 1 1 0 0 delete 2 Subtract 1 from the last 2 digits 0 0 0 0 0 Can figure

AC detailed code is given below:

 

1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 #define N 15 6 struct vertex 7 { 8 int degree; Int index; }v[N]; 11 int cmp(const void *a,const void *b) 12 { 13 return ((vertex*)b)->degree-((vertex*)a)->degree; 14} 15 int main() 16 {17 int r,k,p,q; // loop variable 18 int I,j; // The number of vertices used to determine the edge of the graph is 19 int d1; Int T,n; // The degree of the first vertex after the rest of the sequence is sorted. Int Edge[n][n],flag; 22 scanf("%d", &t); 23 while(T--) 24 { 25 scanf("%d",&n); 26 for(i=0; i<n; i++) 27 { 28 scanf("%d",&v[i].degree); 29 v[i].index=i; 31 memset(Edge,0,sizeof(Edge)); Flag =1; 33 for(int k=0; k<n&&flag; k++) 34 { 35 qsort(v+k,n-k,sizeof(vertex),cmp); I =v[k].index; D =v[k]. Degree; If (d1>n-k-1)// If (d1>n-k-1)// If (d1>n-k-1)// If (d1>n-k-1)// If (d1>n-k-1) 40 for(r=1; r<=d1&&flag; r++) 41 { 42 j=v[k+r].index; If (v[k+r]. Degree <=0)// If (v[k+r]. Degree <=0)// If (v[k+r]. Degree <=0) 45 v[k+r].degree--; 46 Edge[i][j]=Edge[j][i]=1; 47} 48} 49 if(flag) 50 {51 puts("YES"); 47} 48} 49 if(flag) 50 {51 puts("YES"); 52 for(p=0; p<n; p++) 53 { 54 for(q=0; q<n; q++) 55 { 56 if(q) 57 printf(" "); 58 printf("%d",Edge[p][q]); // Prints the adjacency matrix 59} 60 puts(""); // Use printf("\n"). 61 } 62 } 63 else puts("NO"); 64 if(T) 65 puts(""); // line break 66} 67 return 0; 68}Copy the code

Reprint please indicate the: www.cnblogs.com/ECJTUACM-87…