HDU 2454 Degree Sequence of Graph G （可简单图化的判定 havel定理）

题目链接：HDU 2454 Degree Sequence of Graph G

题意：给出N个点的度（简单图），问能能否画出个图，（其实就是给出一个串非负的序列是否有对应的图存在）

没见过这个定理 题意真的难懂。

havel定理就是一个给出一串非负的序列，存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。简单图的话就是，可简单图化。

可简单图化的判定（Havel定理）：把序列排成不增序，即d1>=d2>=……>=dn，则d可简单图化当且仅当d’={d2-1，d3-1，……d(d1+1)-1， d(d1+2)，d(d1+3)，……dn}可简单图化。简单的说，把d排序后，找出度最大的点（设度为d1），把它与度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。

注意：

1.图的总度是偶数。

2.每个点的度不超过N-1。

3.非下降排序，依次删边。若出现负度就是不合法的

AC代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int t,n,i,j;
    int a[1010],flag;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        for(i=0; i<n; i++)
        {
            if(a[i]>n)
                break;
        }
        if(i<n)
        {
            printf("no\n");
            continue;
        }
        for(i=0; i<n; i++)
        {
            int cnt=0;
            flag=0;
            sort(a,a+n,cmp);
            for(j=1; j<n; j++)
            {
                if(cnt==a[0])
                    break;
                a[j]--;
                if(a[j]<0)
                {
                    flag=1;
                    break;
                }
                cnt++;
            }
            if(cnt==0)
                break;
            if(flag)
                break;
            a[0]-=cnt;
        }
        if(flag)
        {
            printf("no\n");
            continue;
        }
        for(i=0; i<n; i++)
        {
            if(a[i])
                break;
        }
        if(i<n)
            printf("no\n");
        else
            printf("yes\n");

    }
    return 0;
}

/*
4
4 3 2 1 1
*/