Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

关键是Havel定理,贪心一次ac,晒代码

Posted by 962861784 at 2011-05-30 09:20:15 on Problem 1659
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int g[11][11];
int n;
struct node
{
	int pos;
	int degree;
};
node d[11];
int cmp(node a,node b)
{
	return (a.degree>b.degree);
}
int main()
{
	
	//freopen("1.txt","r",stdin);
	int tc,i,j,temp;
	scanf("%d",&tc);
	while(tc--)
	{
		scanf("%d",&n);

		for(i=0;i<n;i++)
		{
			scanf("%d",&temp);
			d[i].degree=temp;
			d[i].pos=i;
		}

		sort(d,d+n,cmp);

		memset(g,0,sizeof(g));

		bool flag=true;
		//solve
		for(i=0;i<n;i++)
		{
			sort(d,d+n,cmp);
			if(d[0].degree==0)break;

			for(j=1;j<n;j++)
			{
				d[j].degree--;
				if(d[j].degree<0)
				{
					flag=false;
					break;
				}
				g[d[0].pos][d[j].pos]=g[d[j].pos][d[0].pos]=1;
				d[0].degree--;
				if(d[0].degree==0)break;
			}

			if(!flag)
				break;
		}
		if(!flag)
			printf("NO\n");
		else
		{
			printf("YES\n");
			for(i=0;i<n;i++)
			for(j=0;j<n;j++)
			{
				if(j<n-1)
					printf("%d ",g[i][j]);
				else
					printf("%d\n",g[i][j]);
			}
		}
		printf("\n");
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator