hdu 2454 Degree Sequence of Graph G（可简单图化判定）

•Havel-Hakimi定理：

给定一个非负整数序列{d1,d2,...dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。

进一步，若图为简单图，则称此序列可简单图化。

定理描述：

由非负整数组成的有限非递增序列，S={d1,d2,d3...dn}，当且仅当S1={d2-1,d3-1...d(d1+1),d(d1+2)......dn}也是可图的，

也就是说，序列S1也是由非负整数组成的有限非递增序列，S1是由S的删除第一个元素d1之后的前d1个元素分别减一后得到的序列。

实例：

判断 4 4 3 3 2 是否可图化

首先按非升序排列 4 4 3 3 2

删除4，然后把前4大的数-1 变为：3 2 2 1

然后删除3，把前3大的数-1 变为：1 1 0

删除1，把前1大的数删除变为：1 0

删除1，把前1大的数删除变为： 0

所以是可图化的

判断 5 4 5 2 3 1 是否可图化

首先按非升序排列 5 5 4 3 2 1

删除5，然后把前5大的数-1 变为：4 3 2 1 0

然后删除4，把前4大的数-1 变为: 2 1 0 -1

出现了负数，不可图化

判断 9 4 5 2 3 1 是否可图化

首先按非升序排列 9 5 4 3 2 1

删除9，然后把前9大的数-1 ，但数不够前9大，

也就是会出现负数

不可图化

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 ll a[2005];
 5 int n;
 6 bool Slove()
 7 {
 8     for(int i=0;i<n;++i)
 9     {
10         sort(a+i,a+n,greater<int>());//非增序排列
11         if(a[i]==0)
12             return true;
13         if(i+a[i]>=n)               //不存在前a[i]大个数
14             return false;
15         for(int j=i+1;j<=i+a[i];++j)//前a[i]的数大-1
16         {
17             a[j]--;
18             if(a[j] < 0)
19                 return false;
20         }
21     }
22 }
23  
24  
25 int main()
26 {
27     int t;
28     scanf("%d",&t);
29     while(t--)
30     {
31         scanf("%d",&n);
32         ll sum=0;
33         for(int i=0;i<n;i++)
34         {
35             scanf("%lld",a+i);
36             sum+=a[i];
37         }
38  
39         if(sum%2)
40         {
41             puts("no");
42             continue;
43         }
44  
45         if(Slove())
46             puts("yes");
47         else
48             puts("no");
49     }
50 }

View Code

hdu 2454 Degree Sequence of Graph G（可简单图化判定）

•Havel-Hakimi定理：

•代码