首页 > 代码库 > Havel-Hakimi定理 hdu2454 / poj1695 Havel-Hakimi定理

Havel-Hakimi定理 hdu2454 / poj1695 Havel-Hakimi定理

                                        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");
   }
}




Havel-Hakimi定理 hdu2454 / poj1695 Havel-Hakimi定理