Frogs’ Neighborhood
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
我的代码
#include<stdio.h>
int neighbor_num[11];//记录第i只蛤的邻居数量
int map[11][11];//记录水域地图信息
int num;//记录蛤总数
int dfs(int cnt,int t,int k,int next)
//参数说明：
//cnt是第k只蛤要递归的总层数，即处理完前k-1只蛤后第k只蛤的邻居数量
//t是第k只蛤当前的递归层数
//k是蛤的编号
//next是下一个要可能的邻居的起始下标（即上一个已经找到的邻居的下一个）
//返回值为0时表示此情况不可能，返回值为1时表示可行
{
if (t==cnt+1)
//如果当前的蛤已经递归完成
{
//如果此时还有邻居，说明此情况不可能
if(neighbor_num[k]) return 0;
//如果这只蛤已经是最后一只了，说明此情况已经递归完成，且可行，打印结果并结束递归
if (k==num)
{
printf("YES\n");
for (int i =0;i<num;i++)
{
for (int j=0 ;j<num;j++)
{
printf("%d ",map[i][j]);
}
printf("\n");
}
printf("\n");
return 1;
}
else
//如果不是最后一只蛤，那就对下一只蛤进行递归
{
//如果已经找到了就结束递归
if (dfs(neighbor_num[k+1],1,k+1,0)) return 1;
else return 0;
}
}
else
{
for (int i=next;i<num;i++)
//寻找第k蛤的下一个邻居
{
if (neighbor_num[i])
//如果第i蛤有邻居，我们就假设k与i是邻居，进行递归
{
neighbor_num[i]--;
neighbor_num[k]--;
map[i][k]=map[k][i]=1;
//如果已经找到了就结束递归
if (dfs(cnt,t+1,k,i+1)) return 1;
//回溯
neighbor_num[i]++;
neighbor_num[k]++;
map[i][k]=map[k][i]=0;
}
}
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&num);
for (int i=0;i<num;i++)
{
for (int j=0;j<num;j++)
{
map[i][j]=0;
}
}
for (int i=0;i<num;i++)
{
scanf("%d",&neighbor_num[i]);
}
if (!(dfs(neighbor_num[0],1,0,0))) printf("NO\n\n");
}
return 0;
} 我的想法是，对每一只青蛙进行递归，如果它有邻居的话就搜索出它的邻居，将其与其邻居的邻居个数减1，如果不能给这只青蛙找到所有邻居（即递归到出口时仍有邻居数）就回溯。搜索完一只青蛙之后就递归它下一只青蛙，直到找到一种可能的结果或递归完最后一只青蛙。
然后上网搜了一下这道题的解法，发现了新天地。
全新思路
一、Havel–Hakimi算法
以下内容来自于百度！
Havel-Hakimi算法是图论中解决图形实现问题的算法。 也就是说，它回答了以下问题：给定一个非负整数的有限列表，是否有一个简单的图形，使得它的度序列恰好是这个列表。 这里，“度序列”是一个数字列表，对于图的每个顶点，它表示它有多少个邻居。 对于肯定答案，整数列表称为图形。 该算法构造一个特殊的解决方案，如果存在或证明一个人找不到肯定的答案。 这种结构基于递归算法。 该算法由Havel（1955）出版，后来由Hakimi（1962）出版。
介绍
1，Havel-Hakimi定理主要用来判定一个给定的序列是否是可简单图化的。
2，首先介绍一下度序列：若把图 G 所有顶点的度数排成一个序列 S，则称 S 为图 G 的度序列。
3，一个非负整数组成的有限序列如果是某个无向图的序列，则称该序列是可简单图化的。
4，判定过程：（1）对当前数列排序，使其呈递减，（2）从S[2]开始对其后S[1]个数字-1，（3）一直循环直到当前序列出现负数（即不可简单图化的情况）或者当前序列全为0 （可简单图化）时退出。
5，举例：序列S：7,7,4,3,3,3,2,1 删除序列S的首项 7 ，对其后的7项每项减1，得到：6,3,2,2,2,1,0，继续删除序列的首项6，对其后的6项每项减1，得到：2,1,1,1,0，-1，到这一步出现了负数，因此该序列是不可简单图化的。
代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int num,e;
}x[15];
bool map[15][15];
int cmp(node a,node b)
{
if(a.num==b.num)
return a.e<b.e;
return a.num>b.num;
}
int judge(int n)
{
int i,num,tmp;
while(1){
sort(x+1,x+n+1,cmp);
if(!x[1].num)
return 1;//数组全为 0 的情况退出
for(i=2;i<=x[1].num+1;i++){
if(x[i].num>0){
x[i].num--;
map[x[1].e][x[i].e]=map[x[i].e][x[1].e]=1;
}
else
return 0;
}
x[1].num=0;
}
}
int main()
{
int n,t,i,j;
bool flag;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x[i].num);
x[i].e=i;
}
memset(map,0,sizeof(map));
flag=judge(n);
if(flag){
printf("YES\n");
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
printf(j==1?"%d":" %d",map[i][j]);
printf("\n");
}
}
else
printf("NO\n");
if(t)
printf("\n");
}
return 0;
} 二、Erdős–Gallai定理
以下内容来自牛客网
令 为有限多个非负整数组成的非递增序列。
可简单图化当且仅当这些数字的和为偶数，且
，对于任意
都成立。
也不难理解。对前 个点分配度数，除了两两能连
条边外，剩下的度数由后面点的度数补。
因为 非递增，从小到大枚举
，维护
后缀与
取
的和（
都是单调的，维护从哪开始
的结果是
）。就可以
判断了。
反思
这道题用上图论的思想进行搜索就更加简单了。实际上，我原始的算法是Havel–Hakimi算法的复杂化。由于所有点都已经按照邻居数量降序排序，Havel–Hakimi默认是每一个点的邻居都是其后的若干个。而我没有对这些点的邻居数量进行降序排序，因此要多进行一次递归查找可能的邻居。
此外本题的输出格式中要注意每两个输出样例之间都要增加一个换行。