[HDU5823]color II

[HDU5823]color II

题目大意：

你有一个(n)个点的无向图,点的标号从(0)到(n−1)。
对于每一个非空子集(S)，定义(S)的合法染色是对(S)内的每个点染一种颜色，使得(S)中不存在两个同色点间有边相连。

定义(id(S)=sum_{vin S}2^v)，用(f_id(S))表示(S)的染色数。求(sum_{1le id(S)le 2^n-1}f_{id(S) imes233^{id(S)}mod 2^{32}})。

思路：

状压DP，对于每个状态(j)，枚举每一个独立子集(j)，(f_i=min{f_{i-j}+1})。

时间复杂度(mathcal O(3^n))。

小优化：如果一个集合已经是独立集，那么(f_i=1)，不需要枚举子集了。

源代码：

#include<cstdio>
#include<cctype>
#include<climits>
#include<algorithm>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
inline int getdigit() {
	register char ch;
	while(!isdigit(ch=getchar()));
	return ch^'0';
}
const int N=18,base=233;
bool ind[1<<N];
unsigned f[1<<N],g[1<<N],pwr[1<<N];
inline int lowbit(const int &x) {
	return x&-x;
}
int main() {
	for(register int T=getint();T;T--) {
		const int n=getint();
		unsigned ans=0;
		for(register int i=pwr[0]=1;i<1<<n;i++) {
			if(__builtin_popcount(i)==1) {
				f[i]=1;
				for(register int j=g[i]=0;j<n;j++) {
					if(getdigit()) g[i]|=1<<j;
				}
				ind[i]=true;
			} else {
				f[i]=INT_MAX;
				const int lb=lowbit(i);
				g[i]=g[i^lb]|g[lb];
				ind[i]=!(lb&g[i])&&ind[i^lb];
				if(ind[i]) {
					f[i]=1;
				} else {
					for(register int j=i;j;j=(j-1)&i) {
						if(ind[j]) f[i]=std::min(f[i],f[i^j]+1);
					}
				}
			}
			pwr[i]=pwr[i-1]*base;
			ans+=f[i]*pwr[i];
		}
		printf("%u
",ans);
	}
	return 0;
}