1659.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int maxn=10;
int N,deg[maxn],g[maxn][maxn];

bool assign(int depth)
{
	int i,j,t,s;
	int mark[maxn];
	if (depth>=N-1 && deg[N-1]==0) return true;
	if (deg[depth]==0) assign(depth+1);
	s=0;
	for (i=0;i<N;i++) 
		if (deg[i]>0) s++; 
	if (deg[depth]>s) return false;
	for (i=0;i<N;i++) mark[i]=i;
	s=deg[depth]; deg[depth]=0;
	for (i=0;i<N;i++)
		for (j=i+1;j<N;j++){
			if (deg[mark[i]]<deg[mark[j]]){
				t=mark[i]; mark[i]=mark[j]; mark[j]=t;
			}
		}
	int count=0;
	for (i=0;i<s;i++){
		if (deg[mark[i]]==0) continue;
		deg[mark[i]]--; count++;	
		g[depth][mark[i]]=g[mark[i]][depth]=1;
	}
	if (count<s) return false;
	else 
		return assign(depth+1);
}
int main()
{
	int i,j,task;
	bool first=true;
	//freopen("data.in","r",stdin);
	scanf("%d",&task);
	while (task--){
		if (first) first=false;
		else printf("\n");
		scanf("%d",&N);
		int sum=0;
		for (i=0;i<N;i++){
			scanf("%d",&deg[i]);
			sum+=deg[i];
		}
		if (sum%2==1){
			printf("NO\n"); continue;
		}
		memset(g,0,sizeof(g));
		if (assign(0)){
			printf("YES\n");
			for (i=0;i<N;i++)
				for (j=0;j<N;j++) 
					printf("%d%c",g[i][j],(j==N-1) ? '\n':' ');
		}
		else 
			printf("NO\n");
	}
	return 0;
}