CODE THANKS FESTIVAL 2017 G: Mixture Drug

G - Mixture Drug

問題概要

N (<=40) ノードM辺の無向グラフについて，最大独立集合を求める．

解法概要

懇切丁寧な解説スライドに頼りきってしまったが，復習のため自分なりにDPの遷移のお気持ちなど噛み砕いてみる．……と思ったが，解説スライドに全部書いてあったのでソースコードを載せるだけにしておく．解法ブログの意味はまったくないけど半分全列挙とbitDPの練習問題としてちょうど良かったので記録に残す意味でも記事は書いておく．

解説スライドが本当に親切なのでもしわからなくても解説スライドを読み込むことをお勧めします．

ソースコード

#include<iostream>

using namespace std;

int indipendent[1<<20], not_connect[1<<20], max_indipendent_size[1<<20];

int main(){
    int n,m,a,b;
    cin >> n >> m;
    fill(indipendent, indipendent+(1<<20), 1);
    fill(not_connect, not_connect+(1<<20), (1<<n/2)-1);
    for(int gb=0;gb<(1<<n/2);gb++){
        max_indipendent_size[gb] = 0;
        for(int j=0;j<n/2;j++){
            if(gb & (1<<j)) max_indipendent_size[gb]++;
        }
    }
    for(int i=0;i<m;i++){
        cin >> a >> b;
        if(a > b) swap(a,b);
        if(a <= (n+1)/2){
            if(b <= (n+1)/2){
                indipendent[(1 << (a-1)) | (1 << (b-1))] = 0;
            }else{
                not_connect[1 << (a-1)] ^= (1 << (b-1-(n+1)/2));
            }
        }else{
            max_indipendent_size[(1 << (a-1-(n+1)/2)) | (1 << (b-1-(n+1)/2))] = 0;
        }
        
    }

    for(int ga=0;ga<(1<<(n+1)/2);ga++){
        for(int j=0;j<(n+1)/2;j++){
            if(ga & (1 << j)) continue;
            indipendent[ga|(1<<j)] &= indipendent[ga];
        }
    }

    for(int ga=0;ga<(1<<(n+1)/2);ga++){
        for(int j=0;j<(n+1)/2;j++){
            not_connect[ga|(1<<j)] = not_connect[ga] & not_connect[1<<j];
        }
    }

    for(int gb=1;gb<(1<<n/2);gb++){
        for(int j=0;j<n/2;j++){
            if(gb & (1<<j)) continue;
            if(!max_indipendent_size[gb|(1<<j)] || !max_indipendent_size[gb]){
                max_indipendent_size[gb|(1<<j)] = 0;
            }
        }
    }
    for(int gb=0;gb<(1<<n/2);gb++){
        for(int j=0;j<n/2;j++){
            if(gb & (1<<j)) continue;
            max_indipendent_size[gb|(1<<j)] = max(max_indipendent_size[gb], max_indipendent_size[gb|(1<<j)]);
        }
    }

    int ans = 0;
    for(int ga=0;ga<(1<<(n+1)/2);ga++){
        if(!indipendent[ga]) continue;
        int tmpans = 0;
        for(int j=0;j<(n+1)/2;j++) if(ga & (1<<j)) tmpans++;
        tmpans += max_indipendent_size[not_connect[ga]];
        ans = max(tmpans, ans);
    }
    cout << ans << endl;
}

所感

半分全列挙とbitDPの良い練習問題