将顶点进行排序,去掉度m最大的点,依次让其后m个数减1,若后面的某个顶点出现负数的情况或后面的数的个数少于最大的度
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct EDGE
{
int d;//储存度数
int num;//储存位置
}edge[15];
bool cmp(EDGE x,EDGE y)
{
return x.d>y.d;
}
int main()
{
int T,n,i,j;
int d[15][15];
scanf("%d",&T);
while(T--)
{
int flag=1;
memset(d,0,sizeof(d));
scanf("%d",&n);
for (i=0;i<n;i++)
{
edge[i].num=i;
scanf("%d",&edge[i].d);
}
sort(edge,edge+n+1,cmp);//这个很重要,若度数大于后面剩余的数的时候多家进去的那个就其做作用两人
while (edge[0].d && edge[n-1].d>=0)// 排序后若某个点的度数为负数就不用判断后的了
{
int i = 1;
while (edge[0].d--)
{
--edge[i].d;
d[edge[0].num][edge[i].num] = 1;
d[edge[i].num][edge[0].num] = 1;
++i;
}
++edge[0].d;
sort(edge,edge+n,cmp);
}
if(edge[n-1].d<0)
{
printf("NO\n\n");
continue;
}
printf("YES\n");
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
if(j) printf(" %d",d[i][j]);
else printf("%d",d[i][j]);
}
printf("\n");
}
printf("\n");
}
return 0;
}