最大独立集合 速め
696Mediumで書いたもの。38頂点を1000回実行して200ms弱と相当速い。
s[i][j]: 隣接行列
S[i]: 隣接行列を詰め込んだもの
v[i]: 頂点の利用状況
val: 答え
uk: v[i]=0のiを詰め込んだもの
n: 頂点数
int s[40][40]; long long S[40]; int v[40]; int val; int n; long long uk=0; void calc(){ int nm=0; for(int i=0;i<n;i++)if(v[i]==1)nm++; val=max(val,nm); for(int i=0;i<n;i++){ if(v[i]==0&&__builtin_popcountll(uk&S[i])<2){ v[i]=1; uk-=1LL<<i; long long ch=0; for(int j=0;j<n;j++)if(v[j]==0&&s[i][j]){v[j]=2;ch+=1LL<<j;uk-=1LL<<j;} calc(); v[i]=0; uk+=1LL<<i; for(int j=0;j<n;j++)if(ch&(1LL<<j)){v[j]=0;uk+=1LL<<j;} return; } } int dm=1; int at=-1; for(int i=0;i<n;i++){ if(v[i]==0&&__builtin_popcountll(uk&S[i])>=dm){ dm=__builtin_popcountll(uk&S[i]); at=i; } } if(at==-1)return; v[at]=2; uk-=1LL<<at; calc(); v[at]=0; uk+=1LL<<at; v[at]=1; uk-=1LL<<at; long long ch=0; for(int j=0;j<n;j++){ if(v[j]==0&&s[at][j]){ v[j]=2; uk-=1LL<<j; ch+=(1LL<<j); } } calc(); for(int j=0;j<n;j++){ if(ch&1LL<<j){v[j]=0;uk+=1LL<<j;} } v[at]=0;uk+=1LL<<at; }