傳送門

?

?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 變為：3 2 1 -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

?

轉載于:https://www.cnblogs.com/MMMinoz/p/11311804.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu 2454 Degree Sequence of Graph G（可简单图化判定）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。