tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

最大独立集合 速め

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;
}