Havel-Hakimi定理
当年一度热门出如今ACM赛场上的算法。
算法定义：
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，到这一步出现了负数，因此该序列是不可图的。
有2种不合理的情况：
（1）某次对剩下序列排序后。最大的度数（设为d1）超过了剩下的顶点数；
（2）对最大度数后面的d1个数各减1后，出现了负数。
两道模板题：HDU2454（纯裸题） / poj 1695(略微改一下就好了)
模板：
struct Node{
int id,num;
bool operator < (const Node& rhs) const {
if(num == rhs.num)
return id < rhs.id;
return num > rhs.num;
}
}node[MAXN];
int n;
int mp[MAXN][MAXN];
void solve() {
int sum = 0;
for(int i = 0;i < n;++i)
sum += node[i].num;
if(sum & 1) {
puts("NO");
return;
}
int flag = 0;
memset(mp,0,sizeof(mp));
for(int i = 0;i < n;++i) {
sort(node,node + n);
if(0 == node[0].num) {
flag = 1;
break;
}
for(int j = 0;j < node[0].num;++j) {
if(--node[j+1].num < 0) {
flag = 2;
break;
}
mp[node[0].id][node[j+1].id] = mp[node[j+1].id][node[0].id] = 1;
}
node[0].num = 0;
if(flag == 2) break;
}
if(flag == 1) {
puts("YES");
for(int i = 0;i < n;++i)
for(int j = 0;j < n;++j)
printf("%d%c",mp[i][j],j==n-1?'\n':' ');
} else {
puts("NO");
}
}