简单状压dp的思考 - 最大独立集问题和最大团问题

上次说到，一种用状压DP解决任意无向图最大团问题（MCP）的方程是：

注：此处popcountmax代表按照二进制位下1的个数作为关键字比较，即选择二进制位下1的个数多的那一个

\(F_S =popcountmax \{ F_{S/{k}} , F_{i \in (E_k\cap S)} \cup \{k\} \}\)

其中k是S中任选的一个点。可以证明这样一定是最优的。

首先来细细说说这个算法的复杂度。

外层枚举子图S，假设点数为n，找出k的所有属于S的邻居（与之有边直接连接的点）的点集合需要 \(\mathcal O(n)\) 时间，总共为\(\mathcal O(2^nn)\)

其实这里可以把\(\mathcal O(n)\)优化掉。那么显然是要在找邻居上做些工夫了。

n很小，可以用邻接矩阵建图。只不过，把矩阵变成一维，用一维数组的位掩码表示邻居集合。

程序中可以用位掩码来表示较小的集合子集。

比如\((10010)_2 = 18\)这个二进制数字可以表示第1，4个元素选中（从0开始计数），0，2，3未被选中。

计算机中有高效的并行的位运算，计算位运算时会加速。合理运用位运算可以得到\(\mathcal O(\dfrac{n}{32})\)或\(\mathcal O(\dfrac{n}{64})\)这样的复杂度（我也不知道渐进记号能不能这样写:)

如果要求出\(E_k\cap S\)只需将k的邻居位掩码与S的位掩码做集合与操作就可以了。

输入并建立补图的位掩码代码实现

scanf("%d%d",&n,&m);

for(i=1; i&lt;=m; i++)

	scanf("%d%d",&u,&v),gr[u][v]=gr[v][u]=1;

for(i=0; i<n; i++)

	for(j=0; j<n; j++)

		if(!gr[i][j] && i!=j)

			a[i]|=1ll<<j;

MCP的DP：

#define pop __builtin_popcountll

#define ctz __builtin_ctzll

#define ll long long

ll popmax(ll x,ll y){if(pop(x)<pop(y))return y;else return x;}

void mcp(int x,ll f[]) {

	for(int i=0,c,d; i<(1ll<<x); i++) {

		d=i&(-i);

		c=ctz(d);

		f[i]=popmax(f[i^d],f[(i^d)&a[c]]|d);

	}

}

__builtin_popcountll 可以快速得出long long型数的二进制位下1的个数，可以看做 \(\mathcal O(1)\)。

__builtin_ctzll 可以快速得出long long型数的末尾0的个数，也可以看做 \(\mathcal O(1)\)。

i&(-i)是一种获取i中其中一位的方法，其它的也可以，然后就能解决 \(n \leq 26\) 的部分了。

要达到更优一点的复杂度要用到折半搜索或者在CodeForces上叫做 Meet-in-the-middle。

把原图分成两部分，分别做MCP的DP，之后进行合并：假如把分成的两部分说成是S1，S2，那么遍历S1中的点，找到S2中与S1中所有点都有直接连边的点的集合，做集合并操作。这里的问题不在于集合并操作，而在于找到S2中与S1中所有点都有直接连边的点的集合。倘若与S1中所有点都有直接连边的点的集合用\(G_{S_1}\)表示，那么\(G_{S_1} = G_{S_1/{k}} \cap E_k\),进一步用\(G_{S_1}\cap S_2\)求出S2中与S1中所有点都有直接连边的点的集合。

复杂度都是\(\mathcal O(\sqrt{2^n})\)

最后存边要用另外的方法，下面是可AC的完整代码：

（因为最初发在Guide上，注释英文，有错望告知）

#include <cstdio>

#define ll long long

#define pop __builtin_popcountll

#define ctz __builtin_ctzll

int gr[2006][1010];

ll a[2006];

ll popmax(ll x,ll y){if(pop(x)<pop(y))return y;else return x;}

void mcp(int x,int dt,ll f[]){for(int i=0,c,d;i<(1<<x);i++) d=i&(-i),c=ctz(d),f[i]=popmax(f[i^d],f[(i^d)&a[c+dt]>>(dt)]|d);}

//(Supplementary notes)Bitmask DP to solve MCP in O(2^n)

//f[S] = any possible MIS in S subgraph (f[S] is a set)

//choose any point in S called D

//if D isn't chosen F[S] = F[S/{D}]

//otherwise F[S] = F[D's neighbour in S]∪{D}

void print_mask(ll ans){printf("%d\n",pop(ans));while(ans) printf("%d ",ctz(ans)),ans-=ans&(-ans);}

ll f[1<<22],f2[1<<22],com[1<<22];

int main(){

	int n,m,u,v,i,j,n1,n2;

	scanf("%d%d",&n,&m),n1=n/2,n2=n-n1;

	for(i=1;i<=m;i++) scanf("%d%d",&u,&v),gr[u][v]=gr[v][u]=1;

	for(i=0;i<n;i++) for(j=0;j<n;j++) if(!gr[i][j]&&i!=j) a[i]|=1ll<<j;

	//1.use bit mask to represent complement graph

	//now is to solve a Maximum Clique Problem(MCP)

	mcp(n1,0,f),mcp(n2,n1,f2);

	//2.Bitmask DP

	ll ans=0;

	for(com[0]=(1ll<<n)-1,i=1ll;i<(1ll<<n1);i++) com[i]=com[i-(i&(-i))]&a[ctz(i)];

	for(i=0;i<(1ll<<n1);i++) ans=popmax(ans,(f2[com[i]>>n1]<<n1)|f[i]);print_mask(ans);

	//3.Meet-int-the-middle

	//loop every subsets called S1,construct S2

	//of all nodes of the second half which have edges to all the nodes in S1

	//(so that together they still form a clique shared by both halves)

	//find the maximum answer

	return 0;

}

COCI 2016 Burza

IOI 2007 Training

上面两道题目也是星级推荐的题目，如果练练手挺适合的。

巴特西

简单状压dp的思考 - 最大独立集问题和最大团问题 - 贰

最新文章

热门文章