关于题意和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;}
}
}
}

POJ 1659 Havel-Hakimi定理-LMLPHP

05-11 19:24