Frogs’ Neighborhood
Time Limit: 5000MS |
Memory Limit: 10000K |
|||
Total Submissions: 7615 |
Accepted: 3267 |
Special Judge |
Description
未名湖附近共有
N
个大小湖泊
L
1
,
L
2
, …,
L
n
(其中包括未名湖),每个湖泊
L
i
里住着一只青蛙
F
i
(1 ≤
i
≤
N
)。如果湖泊
L
i
和
L
j
之间有水路相连,则青蛙
F
i
和
F
j
互称为邻居。现在已知每只青蛙的邻居数目
x
1
,
x
2
, …,
x
n
,请你给出每两个湖泊之间的相连关系。
Input
第一行是测试数据的组数
T
(0 ≤
T
≤ 20)。每组数据包括两行,第一行是整数N(2 <
N
< 10),第二行是
N
个整数,
x
1
,
x
2
,…,
x
n
(0 ≤
x
i
≤
N
)。
Output
对输入的每组测试数据,如果不存在可能的相连关系,输出”NO”。否则输出”YES”,并用
N
×
N
的矩阵表示湖泊间的相邻关系,即如果湖泊
i
与湖泊
j
之间有水路相连,则第
i
行的第
j
个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。
Sample Input
3 7 4 3 1 5 4 2 1 6 4 3 1 4 2 0 6 2 3 1 1 2 1
Sample Output
YES 0 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 NO YES 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0
Source
题意:给出无向简单图每个点的度,构造一种图的方案让每个点度满足条件。(简单图即没有重边和自环)
题解:
Havel 定理:
给定一个非负整数
序列{dn},若存在一个无向图使得图中各点的度与此序列一一对应,则称此序列可图化。进一步,若图为简单图
,则称此序列可简单图化
可图化的判定:d1+d2+……dn=0(mod 2)。关于具体图的构造,我们可以简单地把奇数度的点配对,剩下的全部搞成自环。
可简单图化的判定(Havel定理):把序列排成不增序,即d1>=d2>=……>=dn,则d可简单图化当且仅当
d’={d2-1,d3-1,……d(d1+1)-1, d(d1+2),d(d1+3),……dn}可简单图化。简单的说,把d排序后,找出度最大的点(设度为d1),把它与度次大的d1个点之间连边,然后这个点就可以不管了,一直继续这个过程,直到建出完整的图,或出现负度等明显不合理的情况
无向简单图的性质:
设图中每个点为v1,v2,v3…….vk。
设每个点的度为d1,d2,…….dn ;
且:d1>=d2>=d3>=d4…..>=dn
对于任意一个无向简单图来说,一定可以让图中点的度数不变的情况下,改变图的结构,让v1与v2,v3,…..v(d1+1)相连。
具体证明:假设存在i<j,v1与vj相连,v1与vi没有相连。那么由于di>=dj,一定存在vk,使得vk与vi相连,vk与vj不相连。那么我们可以删除v1与vj的边和vk与vi的边,将v1和vi相连,vk和vj相连。这样图中每个点的度数都不会改变,但是我们可以让不存在i<j,v1与vj相连,v1与vi没有相连。
有了以上性质,就很容易证明Havel定理了。
代码如下:
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stack>
#define nn 110
#define inff 0x3fffffff
using namespace std;
int n;
struct node
{
int id,val;
}a[15];
bool cmp(node xx,node yy)
{
return xx.val>yy.val;
}
int ans[15][15];
int main()
{
int i,j;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i].val);
a[i].id=i;
}
memset(ans,0,sizeof(ans));
for(i=1;i<=n;i++)
{
sort(a+i,a+n+1,cmp);
for(j=i+1;j<=n;j++)
{
if(a[i].val==0)
break;
if(a[j].val)
{
a[i].val--;
a[j].val--;
ans[a[i].id][a[j].id]++;
ans[a[j].id][a[i].id]++;
}
}
if(a[i].val)
break;
}
if(i<=n)
puts("NO");
else
{
puts("YES");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d%c",ans[i][j],j==n?'\n':' ');
}
}
}
if(t>0)
puts("");
}
return 0;
}