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;
}