(Havel-Hakimi 定理)
由非负整数组成的非增序列s:d1, d2, …, dn(n ≥ 2, d1 ≥ 1)是可图的,当且仅当序列
s1: d2 – 1, d3 – 1, …, dd1+1 – 1, dd1+2, …, dn
是可图的。序列s1 中有n-1 个非负整数,s 序列中d1 后的前d1 个度数(即d2~dd1+1)减1 后构成
s1 中的前d1 个数。
不可图的情况:
(1)某次对剩下序列排序后,最大的度数(设为d1)超过了剩下的顶点数;
(2) 对最大度数后面的d1 个度数各减1 后,出现了负数。
例如:
(1)序列s:7, 7, 4, 3, 3, 3, 2,最大的度数为7,而除去最大度数7之后,序列s1:7,4,3,3,3,2只有6个元素,小于7,不可图。
(2)序列s:7,7,4,3,3,3,2,1,最大度数为7,序列s可图当且仅当s1:6,3,2,2,2,1,0可图,s1可图仅当s2:2,1,1,1,0,-1可图,显然s2中有负数,s2不可图,所以s不可图。
应用:
青蛙的邻居(Frogs'
Neighborhood)
题目描述:
未名湖附近共有n 个大小湖泊L1, L2, ..., Ln(其中包括未名湖),每个湖泊Li 里住着一只青蛙
Fi(1≤i≤n)。如果湖泊Li 和Lj 之间有水路相连,则青蛙Fi 和Fj 互称为邻居。现在已知每只青蛙的
邻居数目x1, x2, ..., xn,请你给出每两个湖泊之间的相连关系。
输入描述:
第一行是测试数据的组数t(0 ≤ t ≤ 20)。每组数据包括两行,第一行是整数n(2 ≤ n ≤ 10),
第二行是n 个整数,x1, x2,..., xn(0 ≤ xi < n)。
输出描述:
对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"。否则输出"YES",并用n×n
的矩阵表示湖泊间的相邻关系,即如果湖泊i 与湖泊j 之间有水路相连,则第i 行的第j 个数字为
1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。
相邻两组测试数据之间输出一个空行。
样例输入:
2
7
4 3 1 5 4 2 1
6
4 3 1 4 2 0
样例输出:
YES
0 1 1 1 1 0 0
1 0 0 1 1 0 0
1 0 0 0 0 0 0
1 1 0 0 1 1 1
1 1 0 1 0 1 0
0 0 0 1 1 0 0
0 0 0 1 0 0 0
NO
很明显这个题目给的序列是湖泊的度数,应用HAVEL-HAKIMI定理即可。
c++代码:
#include<iostream> #include<string> #include<sstream> #define N 15 using namespace std; //此结构包括每个湖泊的编号和度数 struct Node { unsigned int index; int degree; } nodes[N]; int Edge[N][N];//邻接矩阵 int Cmp(const void* a,const void* b) { return ((Node*)b)->degree -((Node*)a)->degree; } int main() { int nTest,nLake;//,测试数目,湖泊数目 bool flag; cin>>nTest; string line; while(nTest--){ cin>>nLake; getline(cin,line);//跳到下一行 getline(cin,line); istringstream ss(line); //初始化 for(int i=0;i<nLake;i++){ ss>>nodes[i].degree; nodes[i].index=i; } memset(Edge,0,sizeof(Edge)); flag=true; for(int i=0;i<nLake&&flag;i++){ //对nodes 数组后n-i个元素按非递增顺序排序 qsort(nodes+i,nLake-i,sizeof(Node),Cmp); int maxDegree=nodes[i].degree; unsigned int index=nodes[i].index; //某次对剩下序列排序后,最大的度数(设为d1)超过了剩下的顶点数; if(maxDegree>nLake-i-1){ flag=false; break; } for(int k=1;k<=maxDegree&&flag;++k){ int j=i+k; if(nodes[j].degree<0){ flag=false; break; } nodes[j].degree--; Edge[index][nodes[j].index]=Edge[nodes[j].index][index]=1; } } if(flag){ cout<<"YES"<<endl; for(int i=0;i<nLake;++i){ for(int j=0;j<nLake;++j){ cout<<Edge[i][j]<<" "; } cout<<endl; } }else{ cout<<"NO"<<endl; } } char c=getchar(); }