Havel 算法

Havel 算法小记

其实是一个不太重要的算法：
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，到这一步出现了负数，因此该序列是不可图的。

HDU 2454

AC code：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;
int a[maxn];
inline bool cmp(const int &a,const int &b){
return a > b;
}
int main(){
int T,n,sum;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
sum = 0;
for(int i = 0; i < n; ++i){
scanf("%d",&a[i]);
sum += a[i];
}
if(sum & 1){
puts("no");
continue ;
}
int flag = 1;
for(int i = 0; i < n; ++i){
sort(a,a+n,cmp);
if(!a[0]){
flag = 1; break;
}
for(int j = 1; j <= a[0]; ++j){
if(--a[j] < 0){
flag = 2; break;
}
}
if(flag == 2) break;
a[0] = 0;
}
printf("%sn",flag == 1 ?"yes":"no");
}
return 0;
}

POJ 1659

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000 + 5;
struct Node{
int id,de;
bool operator < (const Node &d) const{
if(de == d.de) return id < d.id;
return de > d.de;
}
}a[maxn];
int g[maxn][maxn];
int main(){
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 0; i < n; ++i){
scanf("%d",&a[i].de);
a[i].id = i;
}
memset(g,0,sizeof(g));
bool ok = true;
while(true){
sort(a,a+n);
if(!a[0].de) break;
for(int i = 1; i <= a[0].de; ++i){
if(--a[i].de < 0){
ok = false;
break;
}
g[a[0].id][a[i].id] = g[a[i].id][a[0].id] = 1;
}
if(!ok) break;
a[0].de = 0;
}
if(ok){
puts("YES");
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
printf("%d%c",g[i][j],(j == n - 1) ? 'n' : ' ');
}
}
}
else{
puts("NO");
}
if(T) putchar('n');
}
return 0;
}

最后

以上就是清秀汉堡为你收集整理的Havel 算法的全部内容，希望文章能够帮你解决Havel 算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。