2019牛客第五场E题(independent set1) 图论

题意：给一个图有n个点m条边()，求这张图的所有Induced subgraph（诱导子图？）的最大独立集大小的和

题解：n出到26显然是为了卡掉naive的 的做法，所以我们必须用 的转移。注意到本题是求最大独立集，于是就有一个很好的性质：对于一个子图我们可以随机选择这张子图的任何一个点，根据这个点在或者不在最大独立集里面来将子图转化为两个规模更小的子问题

如果用一个数组stat[i] 来记录和点i 相邻的所有点，于是有dp[s]=max(dp[s-(1<<i)],dp[s&(~stat[i])]+1)。 前一项是这个点不在最大独立集里面，那么直接把这个点从子图上去掉，第二项是说这个点在最大独立集里面，那么把和这个点相邻的点都从子图上抠掉。这样就完成了转移。

#include <iostream>
using namespace std;
const int maxn=1<<26;
uint8_t dp[maxn];
int stat[maxn];

inline uint8_t max(uint8_t a,uint8_t b){
    if(a>b)
        return a;
    return b;
}

int main(){
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    while(m--){
        int x, y;
        cin >> x >> y;
        stat[x] |= 1 << y;
        stat[y] |= 1 << x;
    }
    for(int i=0;i<n;i++){
        stat[i]|=1<<i;
    }
    int up = 1 << n;
    for (int s = 1; s < up;s++){
        int id = __builtin_ffs(s)-1;
        dp[s] = max(dp[s - (1<<id)], dp[s & (~stat[id])] + 1);
    }
    int ans = 0;
    for (int s = 1; s < up;s++){
        ans += dp[s];
    }
    cout << ans<<endl;
}