Frogs' Neighborhood
| Time Limit: 5000MS | Memory Limit: 10000K | |||
| Total Submissions: 10239 | Accepted: 4272 | Special Judge | ||
Description
未名湖附近共有N个大小湖泊L1, L2, ..., Ln(其中包括未名湖)，每个湖泊Li里住着一只青蛙Fi(1 ≤ i ≤ N)。如果湖泊Li和Lj之间有水路相连，则青蛙Fi和Fj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, ..., xn，请你给出每两个湖泊之间的相连关系。
Input
第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行，第一行是整数N(2 < N < 10)，第二行是N个整数，x1, x2,..., xn(0 ≤ xi ≤ 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
分析：n这么小，暴力都可以过的吧......简化一下题意就是告诉每个点的度数，要求连成一个简单图，不能有自环重边，问怎么连.
需要解决的两个问题:1.大的度数到最后可能分配不完 2.会有重边. 对于第一个问题，我们把所有点按照度数排序,对于第二个问题，强行给每个点的连边规定一个方向：每个点向排序好的后面的点连边.总的算法就是先排序，设第i个点的度数为du[i],那么每一轮序列的第一个点向以后的du[i]个点各连一条边，就把当前考虑的点给消掉了，再把剩下的点按照度数排序.如果中途一个点的度数＞剩下的点的个数则无解，或是一个点的度数变成了负数也是无解.
事实上这种方法是Havel-Hakimi定理，用于解决一个度数序列是否可图.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int T, n,a[][];
bool flag = true; struct node
{
int du, id;
}e[]; bool cmp(node x, node y)
{
return x.du > y.du;
} void solve()
{
for (int i = ; i <= n; i++)
{
sort(e + i + , e + n + , cmp);
if (e[i].du > n - i)
{
flag = false;
return;
}
for (int j = i + ; j <= min(n,i + e[i].du); j++)
{
if (e[j].du <= )
{
flag = false;
return;
}
e[j].du--;
a[e[i].id][e[j].id] = a[e[j].id][e[i].id] = ;
}
e[i].du = ;
}
} void print()
{
puts("YES");
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
printf("%d ", a[i][j]);
printf("\n");
}
} int main()
{
scanf("%d", &T);
while (T--)
{
memset(a, , sizeof(a));
flag = true;
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
scanf("%d", &e[i].du);
e[i].id = i;
}
solve();
if (!flag)
puts("NO");
else
print();
printf("\n");
} return ;
}