Algoogle

Algorithm for Programming Contest

彩色数

基本情報


計算量
空間

N := 頂点数

解説


頂点数Nのグラフの彩色数を求める.
試しに塗ってみるのではなく, 包除原理を用いることによって求める.
指数時間アルゴリズム入門(P58)を参照のこと.

自明な枝刈り探索によって指数の底を1.6ぐらいに落とせるらしい.

コード


(graph-coloring.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int MAX_V=16;
const int mod = 10009;
int N[MAX_V], I[1<<MAX_V], V;
inline int mpow(int a, int k) { return k==0? 1: k%2? a*mpow(a,k-1)%mod: mpow(a*a%mod,k/2); }

bool can(int k) {
    int res = 0;
    for(int S=0;S<(1<<V);++S) {
        if(__builtin_popcount(S)%2) res -= mpow(I[S], k);
        else res += mpow(I[S],k);
    }
    return (res%mod+mod)%mod;
}

int color_number() {
    memset(I, 0, sizeof(I));
    I[0] = 1;
    for(int S=1;S<(1<<V);++S) {
        int v = 0;
        while(!(S&(1<<v))) v++;
        I[S] = I[S-(1<<v)] + I[S&(~N[v])];
    }
    int lb = 0, ub = V, mid;
    while(ub-lb>1){
        mid = (lb+ub)/2;
        if(can(mid)) ub = mid;
        else lb = mid;
    }
    return ub;
}

問題


Comments