| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
关键是Havel定理,贪心一次ac,晒代码#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator