【题目链接】
http://acm.hdu.edu.cn/showproblem.php?pid=2454
【别人博客粘贴过来的】
博客地址：https://www.cnblogs.com/debugcool/archive/2011/04/23/HDOJ2454.html
一句话，顶点的度序列 Havel 定理~
定义：给出一个无向图的顶点度序列 {dn}，要求判断能否构造出一个简单无向图。
分析：
贪心的方法是每次把顶点按度大小从大到小排序，取出度最大的点Vi，依次和度较大的那些顶点Vj连接，同时减去Vj的度。连接完之后就不再考虑Vi了，剩下的点再次排序然后找度最大的去连接……这样就可以构造出一个可行解。
判断无解有两个地方，若某次选出的Vi的度比剩下的顶点还多，则无解；若某次Vj的度减成了负数，则无解。
至于什么是Havel定理，上面这个构造过程就是了~
定理的简单证明如下:
(<=)若d'可简单图化，我们只需把原图中的最大度点和d'中度最大的d1个点连边即可，易得此图必为简单图。
(=>)若d可简单图化，设得到的简单图为G。分两种情况考虑:
(a)若G中存在边，则把这些边除去得简单图G'，于是d'可简单图化为G'
(b)若存在点Vi,Vj使得i=dj，必存在k使得(Vi, Vk)在G中但(Vj,Vk)不在G中。这时我们可以令GG=G-{(Vi,Vk),(V1,Vj)}+{(Vk,Vj),(V1,Vi)}。GG的度序列仍为d，我们又回到了情况(a)。
【自己的理解】
真的非常感谢上面这位大哥提供的博客解析，不然我都自闭一下午了。
其实如果单纯想的话我只是想到匹配罢了，根本想不到居然可以有这样的定理。
这个Havel定理，其实是一个判断依据。
1、按照度数从大到小排序，然后依次建边。
2、建边的过程就是以该点为起点，其余都是它的目标点，然后大家都度减一
注意！！！！一定是前k大的。
最后就是判断这个度数组，是否为全零。
下面就是代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std ; const int N = 1e3 + ;
int a[N] ; int main()
{
int T , n ;
for ( cin >> T ; T ; T-- ){
int tot = , edge = ;
cin >> n ;
//for( int i=1;i<=n;i++ ) cin >> a[i] ; for( int i=;i<=n;i++ ){
cin >> a[i] ;
tot += a[i] ;
} // 判断 入度和出度
if( tot & ) {
printf("no\n");
continue;
}
// 排序，从大到小
sort ( a+, a++n , [](int u,int v){return u>v;} ); bool flag = true ;
for(int i = ; flag && i <= n ; i++ ){
for(int j=i+ ; a[i] && j<=n ;j++ ){
if( a[j] == ) continue;
a[i] -- ;
a[j] -- ;
}
//注意每次操作完都需要取前K大的.
sort( a+i+ , a++n ,[](int u,int v){return u>v;} ) ;
}
for(int i=;i<=n;i++){
//cout << a[i] << " ";
if( a[i] != ){
flag = false ;
}
}
if( flag ) puts("yes");
else puts("no");
}
return ;
}
Degree Sequence of Graph G