传送门

 

•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大的数-1 变为：3 2 2 1

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

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

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

所以是可图化的

•代码

 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)
14             return false;
15         for(int j=i+1; j<=i+a[i] ; ++j)
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         int zero=0;
34         for(int i=0;i<n;i++)
35         {
36             scanf("%lld",a+i);
37             if(a[i]==0)
38                 zero++;
39             sum+=a[i];
40         }
41  
42         if(sum%2)
43         {
44             puts("no");
45             continue;
46         }
47  
48         if(Slove())
49             puts("yes");
50         else
51             puts("no");
52     }
53 }

View Code