博客

直接用Havel-Hakimi定理,开始运算结果和样例不一样,琢磨了好久才发现此题是special judge!!!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
const int maxn = 11;
using namespace std;
int mat[maxn][maxn];
struct node{
    int id;
    int deg;
}pot[maxn];
bool Cmp(node x,node y){ return x.deg > y.deg;}
bool Havel_Hakimi(int n){
    for(int i=0; i<=n-1; ++i){
        sort(pot+i,pot+n,Cmp);
        if(i+pot[i].deg >= n) return false;
        for(int j=i+1; j<=i+pot[i].deg; ++j){
             --pot[j].deg;
             mat[pot[i].id][pot[j].id] = mat[pot[j].id][pot[i].id] = 1;
             if(pot[j].deg < 0) return false;
        }
    }
    if(pot[n-1].deg != 0) return false;
    return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
         int n;
         bool flag;
         memset(mat,0,sizeof(mat));
         scanf("%d",&n);
         for(int i= 0; i < n; ++i){
              pot[i].id = i + 1;
              scanf("%d",&pot[i].deg);
              if(pot[i].deg > n-1) flag = false;
         }
         if(Havel_Hakimi(n)&&flag){
              printf("YES\n");
              for(int i=1; i<=n; ++i){
                  printf("%d",mat[i][1]);
                  for(int j=2; j<=n; j++)
                      printf(" %d",mat[i][j]);
                      putchar('\n');
                }
         }
         else printf("NO\n");
         if(T) printf("\n");
    }
    return 0;
}