对于图的所有顶点，我们可以统计出每个顶点的度。像这样的一串数字，我们称之为：度序列。那么反过来，给定一个序列，能否判断这个序列是可图的呢？这里有一个定理：Havel-Hakimi定理可以用来判定一个序列是否可图。判定过程：（1）对当前数列排序，使其呈递减，（2）从S【2】开始对其后S【1】个数字-1，（3）一直循环直到当前序列出现负数（即不是可图的情况）或者当前序列全为0 （可图）时退出。

三步走就可以了：

比如序列：4 7 7 3 3 3 2 1

 

第一步：把序列按降序排序。

 

第二步：删除第一个数7。序列变成

 

第三步：从头开始，数7个数，也就是下标：[1,7]把[1,7]区间里的值都减1

由于第一个数已经删除，那么序列变成这样的了：

然后：

重复第一步：排序。

重复第二步：删除第一个数6

重复第三步：从头开始数6个数：也就是下标【1,6】，把区间【1，6】中的数删除。序列变成：

由于已经出现了-1，而一个点的边数（度）不可能为负数。所以，我们就可以判定序列无法构成一个图，所以此序列是不可图的。

下面再举一个例子：

已经排序：

删除第一个数5：

 

把前面5个数减1：

排序：

删除第一个数3：

 

把前面3个数减1：

排序：

删除第一个数1：

把前面1个数减1：

排序：

删除第一个数1：

把前面1个数减1：

排序：

              

依此类推：到最后只剩下：

由此判断该序列是可图的。

Frogs' Neighborhood
Time Limit: 5000MS   Memory Limit: 10000K

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

题意：
告诉每只青蛙有几个邻居(两只青蛙若生活在有水路相连的湖泊中则是邻居)，用矩阵输出
湖泊的相连关系。

分析：
就是已知每个点的度数，判断是否可图。
第一想法是先把邻居多的安排好（贪心），开始没想到图论中的havel定理，只想到先要排序，然后
找到邻居的相应减1，然后直到所有的青蛙都找到邻居就结束这种操作。

#include <cstdio>  
#include <cstring>  
#include <queue>  
#include <cmath>  
#include <stack>  
#include <vector>  
#include <algorithm>
#include <map>  
using namespace std;  

#define INF 0x3f3f3f3f  
#define CLR(a,b) memset(a,b,sizeof(a))  
#define PI acos(-1.0)  
#define LL long long
int f[12][12];
struct node{
	int degree, flag;
}a[12];
bool cmp(node x, node y){
	return x.degree > y.degree;
}
int main(void){
freopen("题.txt", "r", stdin);
	int t, i, j, n;
	scanf("%d", &t);
	while(t--){
		memset(f, 0, sizeof(f));
		scanf("%d", &n);
		for(i = 1; i <= n; i++){
			scanf("%d", &a[i].degree);
			a[i].flag = i;
		}
		bool succ = 1;
		while(1){
			sort(a+1, a+n+1,cmp);
			if(a[1].degree == 0){
				break;
			}
			for(i = 2; i <= a[1].degree+1; i++){
				a[i].degree--;
				f[a[1].flag][a[i].flag] = 1;
				f[a[i].flag][a[1].flag] = 1;
				if(a[i].degree < 0){
					succ = 0;
					break;
				}
			}
			if(!succ) break;
			a[1].degree = 0;
		}
		if(!succ) puts("NO");
		else{
			puts("YES");
			for(i = 1; i <= n; i++){
				for(j = 1; j <= n; j++){
					printf("%d%c", f[i][j], j == n?'\n':' ');
				}
			}
		} 
		if(t != 0){
			printf("\n");
		}
	}
	
	return 0;
}