CODE THANKS FESTIVAL 2017 : G - Mixture Drug

最大クリークはもうライブラリにしようかな…。
https://code-thanks-festival-2017-open.contest.atcoder.jp/tasks/code_thanks_festival_2017_g

問題

N個の薬があり、混ぜてはいけない薬の対が何組が与えられる。
薬の集合のうち、混ぜても問題ない物の最大数を求めよ。

解法

薬を頂点とし、混ぜても問題ない薬同士の間に辺を張ったグラフを考えると、これは最大クリークを求める問題となる。
最大クリークはBitDPと半分全列挙でO(2^N*N^2)で解ける。

なお、Nに関わらず頂点数は40、ただしN以降の番号の薬は何と混ぜても行けない、と考えると頂点数が固定になるので扱いが楽になる。

int ok[40][40];
ll okm[40];

int N,M;
int ma[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(y,N) FOR(x,N) {
		ok[x][y]=x!=y;
		okm[x]|=1LL<<y;
	}
	FOR(i,M) {
		cin>>x>>y;
		ok[x-1][y-1]=ok[y-1][x-1]=0;
		okm[x-1]^=1LL<<(y-1);
		okm[y-1]^=1LL<<(x-1);
	}
	for(int mask=0;mask<1<<20;mask++) {
		int ng=0;
		ma[mask]=-1<<20;
		FOR(i,20) if(mask&(1<<i)) ma[mask] = max(ma[mask],ma[mask ^ (1<<i)]);
		
		FOR(y,20) if(mask&(1<<y)) {
			FOR(x,y) if((mask&(1<<x)) && ok[x][y]==0) ng=1;
		}
		if(ng==0) ma[mask]=__builtin_popcount(mask);
	}
	
	int ret=0;
	for(int mask=0;mask<1<<20;mask++) {
		int ng=0;
		ll tmask=(1<<20)-1;
		FOR(y,20) if(mask&(1<<y)) {
			tmask &= okm[y+20];
			FOR(x,y) if((mask&(1<<x)) && ok[20+x][20+y]==0) ng=1;
		}
		if(ng==0) {
			ret=max(ret,__builtin_popcount(mask)+ma[tmask]);
		}
	}
	cout<<ret<<endl;
}

まとめ

最大クリークは600pt相当なのか…。