【BZOJ4455】【ZJOI2016】小星星

  这题考场上sb写了个状压DP+爆搜，出了考场才反应过来。回去把爆搜改成了状压DP，合并状态，在UOJ上能跑出9个点，BZOJ上刚好能卡过。

  感觉这个做法比较简单就简单地讲一下好了。

  从根节点开始做树形DP，记f[i][j][k]表示树上的编号为i的点，对应原图上编号为j的点，子树（包括这个点）上所有点对应原图上的点的集合为k的方案数，那么从子树到根的状态转移是很显然的。复杂度没仔细地计算过，大概地算了一下还是很理想的。

  直接这么做可能会爆空间，而对于一棵子树，状态数最大是C(n,n/2)级别的，所以存储的时候另开几个数组记录一下状态就好了。

#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=17,maxsta=24311;

long long f[maxn][maxn][maxsta];
int vis[maxn][maxn][1<<maxn],sta[maxn][maxn][maxsta],num[maxn][maxn];
long long tempf[maxn][maxsta];
int tvis[maxn][1<<maxn],tsta[maxn][maxsta],tnum[maxn];
int map1[maxn][maxn],map2[maxn][maxn];
int n,m;

void Merge(int x,int xc,int y,int yc)
{
	int xsta,ysta,nsta;
	for (int i=1;i<=num[x][xc];i++)
		for (int j=1;j<=num[y][yc];j++)
			if (!((xsta=sta[x][xc][i])&(ysta=sta[y][yc][j])))
			{
				nsta=xsta|ysta;
				if (!tvis[xc][nsta]) tvis[xc][nsta]=++tnum[xc],tsta[xc][tnum[xc]]=nsta;
				tempf[xc][tvis[xc][nsta]]+=f[x][xc][i]*f[y][yc][j];
			}
}

void DFS(int x,int fa)
{
	for (int i=0;i<n;i++) if (i!=x && i!=fa && map2[x][i]) DFS(i,x);
	for (int i=0;i<n;i++) vis[x][i][1<<i]=1,sta[x][i][1]=1<<i,f[x][i][1]=1,num[x][i]=1;
	for (int j=0;j<n;j++) if (j!=x && j!=fa && map2[x][j])
	{
		memset(tempf,0,sizeof(tempf));
		memset(tvis,0,sizeof(tvis));
		memset(tnum,0,sizeof(tnum));
		for (int i=0;i<n;i++) for (int k=0;k<n;k++) if (i!=k && map1[i][k]) Merge(x,i,j,k);
		memcpy(f[x],tempf,sizeof(tempf));
		memcpy(vis[x],tvis,sizeof(tvis));
		memcpy(sta[x],tsta,sizeof(tsta));
		memcpy(num[x],tnum,sizeof(tnum));
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),--x,--y,map1[x][y]=map1[y][x]=1;
	for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),--x,--y,map2[x][y]=map2[y][x]=1;
	DFS(0,-1);
	long long res=0;
	for (int i=0;i<n;i++) for (int j=1;j<=num[0][i];j++) res+=f[0][i][j];
	printf("%lld\n",res);
	return 0;
}

  正解还在看...