【BZOJ2576】[JSOI2011]序的计数 （动态规划）

题面

BZOJ

题解

首先构建一个新的虚拟节点连接所有目标节点，强行将其作为第一个被访问的节点，这样子就解决了图不连通的问题。

除了目标节点外，所有其他点都可以缩成一个节点。

这样子的图实际上只有\(k+2\)个节点，\(k+1\)个目标节点。

预处理\(G[S][u]\)表示已经在\(dfs\)序中出现过的点的集合为\(S\)，当前在点\(u\)能够访问到的点。

设\(f[S][u]\)表示当前在点\(u\)，已经确定\(dfs\)序的集合为\(S\)的\(dfs\)序的方案数。

注意如果一个点和不合法的点有连边，那么这个点不能回朔。

转移的时候枚举一个\(u\)的相邻点，记忆化搜索即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define ll long long

#define MAX 120

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,m,K,id[MAX],S[20];

bool g[MAX][MAX],M[20][20];

ll f[1<<19][20];

int G[1<<19][20];

int dfs(int u,int S)

{

	if(~G[S][u])return G[S][u];

	int ret=1<<u;

	for(int i=0;i<K;++i)

		if(M[u][i]&&!(S&(1<<i)))ret|=dfs(i,S|(1<<i));

	return G[S][u]=ret;

}

ll Solve(int u,int S)

{

	if(~f[S][u])return f[S][u];

	if(G[S][u]==1<<u)return S==(1<<K)-1||!M[u][K];

	ll ret=0;

	for(int i=0;i<K;++i)

		if(M[u][i]&&!(S&(1<<i)))

			ret+=Solve(i,S|(1<<i))*Solve(u,S|G[S|(1<<i)][i]);

	return f[S][u]=ret;

}

int main()

{

	n=read();m=read();K=read();K+=1;

	for(int i=1,u,v;i<=m;++i)u=read(),v=read(),g[u][v]=g[v][u]=1;

	for(int i=1;i<=n;++i)id[i]=K;

	for(int i=0;i<K-1;++i)S[i]=read(),id[S[i]]=i,M[i][K-1]=M[K-1][i]=1;

	for(int i=0;i<=K;++i)

		for(int j=1;j<=n;++j)M[i][id[j]]|=g[S[i]][j];

	memset(G,-1,sizeof(G));memset(f,-1,sizeof(f));

	for(int i=0;i<(1<<K);++i)

		for(int j=0;j<K;++j)

			if(i&(1<<j))dfs(j,i);

	printf("%lld\n",Solve(K-1,1<<(K-1)));

	return 0;

}