关于题意和Havel-Hakimi定理，可以看看http://blog.csdn.net/wangjian8006/article/details/7974845

讲得挺好的。

我就直接粘过来了

【

题目大意：给出一个非负整数的序列，问这个序列是否是可图序列，而是否可图根据

Havel-Hakimi定理的方法来构图

解题思路：Havel-Hakimi定理:

1，一个非负整数组成的有限序列如果是某个无向图的序列，则称该序列是可图的。

2，判定过程：

（1）对当前数列排序，使其呈非递增序列

（2）从第二个数开始对其后d[1]个数字减1，d[1]代表排序后第1个数的值

（3）然后删除第一个之后对剩下的数继续排序

（3）一直循环直到当前序列出现负数（即不是可图的情况）或者当前序列全为0 （可图）时退出。

3，举例：

序列S：7,7,4,3,3,3,2,1

删除序列S的首项 7 ，对其后的7项每项减1，

得到：6,3,2,2,2,1,0，

继续删除序列的首项6，

对其后的6项每项减1，

得到：2,1,1,1,0，-1，

到这一步出现了负数，因此该序列是不可图的

再举例：

序列：4 3 1 5 4 2 1

排序之后：5 4 4 3 2 1 1

删除5对后面5个数减1操作

3 3 2 1 0 1

排序

3 3 2 1 1 0

删除3对后面3个数减1操作

2 1 0 1 0

排序

2 1 1 0 0

删除2 对后面2个数减1操作

0 0 0 0

全为0，可图

】

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int flag,n,cas;

bool map[25][25];

struct node{int i,wei;}d[21];

void print()

{

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=n;j++)

            printf("%d ",map[i][j]);

        printf("\n");

    }

    printf("\n");

}

bool cmp(const node &a,const node &b){return a.wei>b.wei;}

int main()

{

    scanf("%d",&cas);

    for(int ii=1;ii<=cas;ii++)

    {

        memset(map,0,sizeof(map));

        scanf("%d",&n);

        for(int i=1;i<=n;i++)

            d[i].i=i,scanf("%d",&d[i].wei);

        while(1)

        {

            flag=1;

            sort(d+1,d+n+1,cmp);

            for(int i=2;i<=1+d[1].wei;i++)

            {

                map[d[1].i][d[i].i]=map[d[i].i][d[1].i]=1;

                d[i].wei--;

                if(d[i].wei<0){flag=2;break;}

            }

            d[1].wei=0;

            if(flag==2){printf("NO\n\n");break;}

            for(int i=1;i<=n;i++)

                if(d[i].wei!=0){flag=0;break;}

            if(flag==1){printf("YES\n");print();break;}

        }

    }

}