题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5823
题意：
给定$n$个点组成的图，求最小染色数。$(1 \le n \le 18)$
分析：
$n$只有$18$，显然状压。
一个很重要的性质是每种颜色的点集是独立集，那么我们可以先预处理出所有独立集，然后对于每个子集，枚举子集的子集，进行转移。
枚举子集的方法：
$i$中第$x$位为$0$表示不在子集中
for(int j = i; j; j = (j - 1) & i)
第$x$位为$1$表示不在子集中
for(int j = i; j < (1 << m); j = (j + 1) | i)
先枚举子集，再枚举子集的子集，时间复杂度$O(3^n)$（$\sum_{k=0}^{n}{\binom{n}{k}2^k}=(1+2)^n=3^n$）
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> #include<iostream> using namespace std; typedef long long ll; typedef unsigned int uint; const int maxn = 18 + 1; char s[maxn]; uint dp[1 << maxn]; uint mul[1 << maxn]; bool ok[1 << maxn]; bool mp[maxn][maxn]; int main (void) { mul[0] = 1; for(int i = 1; i < (1 << 18); i++) mul[i] = mul[i - 1] * 233; int T;scanf("%d", &T); while(T--){ int n;scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%s", s); for(int j = 0; j < n; j++){ mp[i][j] = s[j] - '0'; } } memset(ok, true, sizeof(ok)); memset(dp, 0x3f, sizeof(dp)); for(int i = 0; i < ( 1 << n); i++){ for(int j = 0; j < n; j++){ if((i >> j) & 1){ for(int k = j + 1; k < n; k++){ if((i >> k) & 1 && mp[j][k]){ ok[i] = false; break; } } if(!ok[i]) break; } } } uint res = 0; dp[0] = 0; for(int i = 1; i < (1 << n); i++){ for(int j = i;j; j = (j - 1) & i){ if(ok[j]){ dp[i] = min(dp[i], dp[i ^ j] + 1); } } res += mul[i] * dp[i]; } printf("%u\n", res); } return 0; }
|
