poj 1659 Frogs' Neighborhood

知识扩展：（Havel-Hakimi 定理）由非负整数组成的非增序列 s: d₁, d₂, ··· , d_n (n≥2, d≥1) 是可图的，当且仅当序列 s₁: d₂-1, d₃-1, ··· , d_d1+1-1, d_d1+2, ··· , d_n 是可图的。序列 s₁ 中有 n-1 个非负整数，s 序列中 d₁ 后的前 d₁ 个度数（即 d₂~d_d1+1）减 1 后构成 s₁ 中的前 d₁ 个数。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 struct Edge{
 6     int id,deg;
 7     bool operator <(const Edge& E) const{
 8         return deg>E.deg;
 9     }
10 }e[10];
11 
12 int main(){
13     int t,n,i,j,a[10][10];
14     cin>>t;
15     while(t--){
16         cin>>n;
17         for(i=0;i<n;i++){
18             for(j=0;j<n;j++) a[i][j]=0;
19         }
20         for(i=0;i<n;i++){
21             cin>>e[i].deg;
22             e[i].id=i;
23         }
24         bool flag=true;
25         i=0;
26         while(flag){
27             sort(e+i,e+n);
28             if(e[i].deg==0) break;
29             for(j=i+1;j<=i+e[i].deg;j++){
30                 if(e[j].deg-1>=0){
31                     a[e[i].id][e[j].id]=a[e[j].id][e[i].id]=1;
32                     e[j].deg--;
33                 }
34                 else{
35                     flag=false;
36                     break;
37                 }
38             }
39             i++;
40         }
41         if(!flag) cout<<"NO"<<endl;
42         else{
43             cout<<"YES"<<endl;
44             for(i=0;i<n;i++){
45                 for(j=0;j<n-1;j++) cout<<a[i][j]<<" ";
46                 cout<<a[i][n-1]<<endl;
47             }    
48         }
49         if(t>0) cout<<endl;
50     }
51     return 0;
52 }