Havel—Hakimi定理(度序列)

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

下标 1 2 3 4 5 6 7 8 值 4 7 7 3 3 3 2 1

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

下标 1 2 3 4 5 6 7 8 值 7 7 4 3 3 3 2 1

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

下标 1 2 3 4 5 6 7 值 7 4 3 3 3 2 1

  第三步：从头开始，数7个数，也就是下标：[1,7]把[1,7]区间里的值都减1 由于第一个数已经删除，那么序列变成这样的了：

下标 1 2 3 4 5 6 7 值 6 3 2 2 2 1 0

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

下标 1 2 3 4 5 6 值 2 1 1 1 0 -1

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

5 4 3 3 2 2 2 1 1 1.

删除第一个数5：

4 3 3 2 2 2 1 1 1.

  把前面5个数减1：

3 2 2 1 1 2 1 1 1.

排序：

3 2 2 2 1 1 1 1 1.

删除第一个数3：  

2 2 2 1 1 1 1 1.

把前面3个数减1：

1 1 1 1 1 1 1 1.

排序：

1 1 1 1 1 1 1 1.

删除第一个数1：

1 1 1 1 1 1 1.

把前面1个数减1：

0 1 1 1 1 1 1.

排序：

1 1 1 1 1 1 0

删除第一个数1：

1 1 1 1 1 0

把前面1个数减1：

0 1 1 1 1 0

排序：

1 1 1 1 0 0

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

0 0 0 0

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

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; }