【浙江省选 2016】小星星 / 题解

Libre OJ 题目地址

题意简述

给定一张 $n$ 个点 $m$ 条边的无向图和它的一个生成树。出于某种原因,点的编号在生成树中被打乱了。现在重新给生成树中每个节点编号,求合法方案树。

编号方案合法当且仅当,一对在生成树上有相连的边的点,无向图中对应的点对间也存在一条边。

输入 $n,m$ ,编号混乱的生成树和原来的无向图。输出合法的编号方案数。

本题中,$n \leq 17$。

思路

我们可以定义状态 $dp_{(i,j,S)}$ 表示当生成树中点 $i$ 的新编号为 $j$,子树内已有编号为 $S$ 时,所有的合法方案数。这样暴力转移的时间复杂度为 $\Theta(n^3\times 3^n)$,显然是不够优秀的。

我们需要降低复杂度,直接去掉 $dp$ 数组的第三维。这样不可避免地出现了编号重复的问题,我们需要将不合法的方案从答案中删掉。

那么我们可以利用容斥。枚举最后的编号方案用掉的编号集合 $S$,对包含在 $S$ 中的点进行 $dp$。令确定的 $S$ 的方案数为 $f$,最后的答案就是

$$\sum_{ |S|=n }f-\sum_{ |S|=n-1 }f+\sum_{ |S|=n-2 }f – \cdots$$

总时间复杂度为 $\Theta(n^3 \times 2^n)$。

代码

#include <bits/stdc++.h>
#define maxn 20
#define ll long long
struct Edge{
	int to,next;
	Edge(int a=0,int b=0){
		to=a,next=b;
	}
}l[maxn<<1];
int head[maxn],sta[maxn];
int cnt,n,m,siz;
int mp[maxn][maxn];
ll dp[maxn][maxn],res,sub;
inline void Add(int a,int b){
	l[++cnt]=Edge(b,head[a]);head[a]=cnt;
	l[++cnt]=Edge(a,head[b]);head[b]=cnt;
}
inline void Dfs(int u,int f){
	for (register int i=head[u];i;i=l[i].next){
		if (l[i].to!=f) Dfs(l[i].to,u);
	}
	for (register int s=1;s<=siz;++s){
		int j=sta[s];dp[u][j]=1;
		for (register int i=head[u];i;i=l[i].next){
			int v=l[i].to;if (v==f) continue;
			ll sum=0;
			for (register int k=1;k<=siz;++k)
				sum+=dp[v][sta[k]]*mp[j][sta[k]];
			dp[u][j]*=sum;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for (register int i=1,a,b;i<=m;++i)
		scanf("%d%d",&a,&b),
		mp[a][b]=mp[b][a]=1;
	for (register int i=2,a,b;i<=n;++i)
		scanf("%d%d",&a,&b),Add(a,b);
	for (register int S=0;S<1<<n;++S){
		siz=sub=0;
		for (register int i=1;i<=n;++i)
			if (S>>(i-1)&1) sta[++siz]=i;
		Dfs(1,0);
		for (register int i=1;i<=siz;++i) sub+=dp[1][sta[i]];
		((n-siz)&1)?res-=sub:res+=sub;
	}
	printf("%lld\n",res);
}