当前位置: 代码迷 >> 综合 >> poj 1659 Frogs' Neighborhood 度序列可图化 贪心
  详细解决方案

poj 1659 Frogs' Neighborhood 度序列可图化 贪心

热度:12   发布时间:2024-01-19 06:12:34.0

题意:

对一个无向图给出一个度序列,问他是否可简单图化。

分析:

根据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");}	}		
}