題意：給一個(gè)圖有n個(gè)點(diǎn)m條邊()，求這張圖的所有Induced subgraph（誘導(dǎo)子圖熬丧？）的最大獨(dú)立集大小的和
題解：n出到26顯然是為了卡掉naive的 的做法笋粟，所以我們必須用
的轉(zhuǎn)移。注意到本題是求最大獨(dú)立集析蝴，于是就有一個(gè)很好的性質(zhì)：對于一個(gè)子圖我們可以隨機(jī)選擇這張子圖的任何一個(gè)點(diǎn)害捕，根據(jù)這個(gè)點(diǎn)在或者不在最大獨(dú)立集里面來將子圖轉(zhuǎn)化為兩個(gè)規(guī)模更小的子問題
如果用一個(gè)數(shù)組stat[i] 來記錄和點(diǎn)i 相鄰的所有點(diǎn)，于是有dp[s]=max(dp[s-(1<<i)],dp[s&(~stat[i])]+1)闷畸。 前一項(xiàng)是這個(gè)點(diǎn)不在最大獨(dú)立集里面尝盼，那么直接把這個(gè)點(diǎn)從子圖上去掉，第二項(xiàng)是說這個(gè)點(diǎn)在最大獨(dú)立集里面佑菩，那么把和這個(gè)點(diǎn)相鄰的點(diǎn)都從子圖上摳掉盾沫。這樣就完成了轉(zhuǎn)移。
#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;
}
