思路可以参考上一篇,比那个简单多了。或者自己搜Havel-Hakimi定理。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; struct node { int num,cnt; }p[111]; int n,m; bool l[111][111]; bool cmp(node x,node y){return x.cnt>y.cnt;} void solve() { m=0; for(int i=0;i<n;i++) { sort(p+i,p+n,cmp); int u=p[i].num; for(int j=i+1;j<n;j++) { int v=p[j].num; if(p[i].cnt&&p[j].cnt) { p[i].cnt--;p[j].cnt--; l[u][v]=l[v][u]=1; m++; } else break; } if(p[i].cnt) { printf("NO\n"); return; } } printf("YES\n"); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(l[i][j])printf("1"); else printf("0"); if(j!=n)printf(" "); } printf("\n"); } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(l,0,sizeof(l)); for(int i=0;i<n;i++){scanf("%d",&p[i].cnt);p[i].num=i+1;} solve(); if(t)printf("\n"); } return 0; }