题意:
对一个无向图给出一个度序列,问他是否可简单图化。
分析:
根据Havel定理,直接贪心即可。
代码:
//poj 1659
//sep9
#include <iostream>
#include <algorithm>
using namespace std;
struct Node{int num,ids;
}p[16];
int ans[16][16];
int n;int cmp(Node a,Node b){return a.num>b.num;
}int main()
{int i,j,cases;scanf("%d",&cases);while(cases--){memset(ans,0,sizeof(ans));scanf("%d",&n);for(i=1;i<=n;++i){int d;scanf("%d",&d);p[i].num=d;p[i].ids=i;} int ok; while(1){sort(p+1,p+1+n,cmp); if(p[1].num==0){ok=1;break;}int d=p[1].num,u=p[1].ids;p[1].num=0;if(d>n-1){ok=0;break;}int err=0; for(i=2;i<d+2;++i){--p[i].num; if(p[i].num<0){err=1;break;} ans[u][p[i].ids]=1;ans[p[i].ids][u]=1;}if(err==1){ok=0;break;}} if(ok==0)printf("NO\n\n");else{printf("YES\n");for(i=1;i<=n;++i){for(j=1;j<=n;++j)printf("%d ",ans[i][j]);printf("\n");} printf("\n");} }
}