NOIP2017 宝藏

题面自取

​

一看就是状压DP，但是如何保存深度信息？每个点存深度显然不现实

考虑一个点的深度信息只在加新点时有用，所以强行定义当前所有点的深度即可

\(f_{i,s}\)表示当前所有点深度为\(i\)，连通块集合为\(s\)

显然枚举\(s\)补集的子集\(ss\)，则有 \[ f_{i+1,s+ss}\leftarrow f_{i,s}+g_{ss} \] 其中\(g_{ss}\)表示\(ss\)集合中所有点到\(s\)代价之和，可以预处理出来

​

示例程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=15,maxe=2005,INF=0x3f3f3f3f;
int n,e,f[maxn][4100],d[maxn][maxn],g[4100],w[maxn],lg[4100],stk[4100];
#define up(x,y) (x=min(x,y))
#define lowbit(x) ((x)&-(x))
int main(){
	scanf("%d%d",&n,&e);
	cl(d,63);
	for (int i=1,x,y,z;i<=e;i++) scanf("%d%d%d",&x,&y,&z),x--,y--,up(d[x][y],z),up(d[y][x],z);
	cl(f,63);
	for (int i=0;i<n;i++) f[1][1<<i]=0,lg[1<<i]=i;
	for (int i=1;i<n;i++)
	 for (int s=0;s<(1<<n);s++){
	 	cl(w,63);
	 	for (int j=0;j<n;j++)
	 	 for (int k=s;k;k-=k&-k)
	 	  if (d[j][lg[k&-k]]!=INF) up(w[j],d[j][lg[k&-k]]*i);
	 	int t=s^((1<<n)-1);
	 	cl(g,0); stk[0]=0;
	 	for (int ss=t;ss;ss=(ss-1)&t) stk[++stk[0]]=ss;
	 	for (int j=stk[0];j;j--){
			g[stk[j]]=g[stk[j]^lowbit(stk[j])]+w[lg[lowbit(stk[j])]];
			if (g[stk[j]]>INF) g[stk[j]]=INF;
		}
		for (int ss=t;ss;ss=(ss-1)&t){
			up(f[i+1][s|ss],f[i][s]+g[ss]);
		}
	 }
	int ans=INF;
	for (int i=0;i<=n;i++) up(ans,f[i][(1<<n)-1]);
	printf("%d",ans);
	return 0;
}