解决的是几种NPC/NPH问题,用二进制表示集合,作为状态,复杂度为指数级。

最优配对问题

空间里有n个点P0,P1,P2…,Pn-1,把他们分为n-2对,使所有点对中两点距离之和尽量小。
S表示已选点(下标)的集合,d(S)表示S中的点的最优解
$$d(S)=Min(|P_iP_j|+d(S-{i}-{j}) \,\,|\,\, j \in S,i=Min(S))$$

1
2
3
4
5
6
7
8
9
10

d[0]=0;
for(int S=1;S<(1<<n);++S){
int i,j;
d[S]=INF;
for(i=0;i<n;++i)
if(S&(1<<i)) break;
for(int j=i+1;i<n;++j)
if(S&(1<<j)) d[S]=min(d[S],dist(i,j)+d[S^(1<<i)^(1<<j)]);
}

TSP

经典的NPC难题。
n个城市,两两之间均有道路相连,求一条经过每个城市一次且仅一次,最后回到起点的路线,使得经过道路总长度最短,城市编号0~n-1。
$d_{i,S}$表示以i结尾,经过了S内的点的最短路径

$$d_{j,S} = Min (d_{i,S}+G_{i,j}) \; (i \in S,j \notin S)$$

答案即为Min(d_{0..n,(1<<n)-1})
复杂度为$O(n^22^n)$

  • poj3311
    这里并未强调每个点只能经过一次,先Floyd处理出每两点间的最短距离。

图的染色

一个无向图G,用最少的颜色将图染色,使得相邻结点颜色不同

d(S)表示把结点集S染色所需的最少颜色

$$d(S)=(d(S-S’)+1 \,\,|\,\, S’\subset S) 且S’内无相邻结点(可以染成同一种颜色的结点集) $$

1
2
3
4
5
6
d[0]=0;
for(int S=1;S<(1<<n);++S){
d[S]=INF;
for(int S0=S; S0; S0=(S0-1)&S)
if(no_edges_inside(S0)) d[S]=min(d[S],d[S-S0]+1);
}

  • 枚举1~n每个集合S的所有子集的复杂度为$O(3^n):$
    $$\sum C_n^k2^k=(2+1)^n=3^n$$

二分图完备匹配

完备匹配是指能完全覆盖一边的点的匹配,不要求两边都被完全覆盖

poj2441

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline int next(int n)    // n!=0
{
int x=n&(-n);
return n+x+(n^(n+x))/x/4;
}
int dp()
{
d[0] = 1;
for(int j=1;j<(1<<M);++j)
{
for(int i=1;i<=M;++i)
if(j & (1<<(i-1)) ) d[j] += d[j-(1<<(i-1))]*G[__builtin_popcount(j)][i];
}
int ans = 0;
for(int j = (1<<N)-1 ; j<(1<<M) ; j=next(j) )
{
// printf("%d\n",d[j]);
ans += d[j];
}
return ans;
}

拓扑排序方案数

即给定一些偏序关系,求满足这些偏序关系的排列方案。

$d_S$表示集合S内的点已全部排序的方案数,$d_0 = 1$
$$d_S = \sum d_{S-i} \;\; i的后继不在S中(即i为集合中最后一个结点)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dp()
{
memset(d,0,sizeof d);
d[0] = 1;
for(int i=0;i<(1<<n);++i)
{
for(int j=1;j<=n;++j)
{
int t = G[j]|(1<<(j-1));
if((t&i) == 0 )
{
d[i|(1<<(j-1))] += d[i];
}
}
}
printf("%lld\n",d[(1<<n)-1]);
}

hdu4917

由于n较大而m较小,可以分联通块求解,每个联通块最多有m+1个结点
最后分别乘在一起并乘上相应的组合数 C(remain,size) 即可

zoj1346