【Havel 定理】Degree Sequence of Graph G

【题目链接】

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 + 10 ;
int a[N] ;

int main()
{
    int T , n ;
    for ( cin >> T ; T ; T-- ){
        int tot = 0 , edge = 0 ;
        cin >> n ;
        //for( int i=1;i<=n;i++ ) cin >> a[i] ;

        for( int i=1;i<=n;i++ ){
            cin >> a[i] ;
            tot += a[i] ;
        }


        // 判断  入度和出度
        if( tot & 1 ) {
            printf("no
");
            continue;
        }
        // 排序，从大到小
        sort ( a+1, a+1+n , [](int u,int v){return u>v;} );

        bool flag = true ;
        for(int i = 1 ; flag && i <= n ; i++ ){
            for(int j=i+1 ; a[i] && j<=n ;j++ ){
                if( a[j] == 0 ) continue;
                a[i] -- ;
                a[j] -- ;
            }
            //注意每次操作完都需要取前K大的.
            sort( a+i+1 , a+1+n ,[](int u,int v){return u>v;} ) ;
        }
        for(int i=1;i<=n;i++){
            //cout << a[i] << " ";
            if( a[i] != 0 ){
                flag = false ;
            }
        }
        if( flag ) puts("yes");
        else puts("no");
    }
    return 0;
}