【NOIP2017提高组 day2】宝藏

题目

题解

–这道题不是最小生成树这道题不是最小生成树这道题不是最小生成树
因为修路的代价与它里起点的距离有关，又因为最后的路径一定组成了一棵树
所以我们可以一层层的dp
设f[i][s]：到第i层时，已经连上的集合为s的最优解
转移f[i][s|S]=min(f[i-1][s]+D[s][S]*(i-1))
(D[s][S]是把这两个没有交集的集合相连的最小代价）
D是可以由d预处理出来的（d[i][s]是把i连到s这个集合的最小代价）
直接枚举起点，再向下dp就好

小技巧：枚举一个集合的子集for(int i=s;i;i=(i-1)&s)

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=15;

int n,m;
long long g[MAXN][MAXN];
long long f[MAXN][1<<12],d[MAXN][1<<12],D[1<<12][1<<12];
long long ans=0x7f7f7f7f;


int main(){
	cin>>n>>m;
	memset(g,0x7f,sizeof(g));
	for(int i=1;i<=m;i++){
		int u,v;
		long long l;
		scanf("%d%d%lld",&u,&v,&l);
		g[u][v]=min(g[u][v],l);
		g[v][u]=min(g[v][u],l);
	}
	memset(d,0x7f,sizeof(d));
	int u=(1<<n)-1;
	for(int i=1;i<=n;i++){
		for(int s=0;s<(1<<n);s++){
			for(int j=1;j<=n;j++)
				if((s>>(j-1))&1){
					d[i][s]=min(d[i][s],g[j][i]);
				}
		}
	}
	for(int s=0;s<(1<<n);s++)
		for(int S=s^u;S;S=(S-1)&(s^u))
			for(int i=1;i<=n;i++)
				if((S>>(i-1))&1){
					if(d[i][s]==d[0][0]){
						D[s][S]=0;
						break;
					}
					D[s][S]+=d[i][s];
				}
	for(int r=1;r<=n;r++){
		memset(f,0x7f,sizeof(f));
		f[1][1<<(r-1)]=0;
		for(int i=2;i<=n;i++)
			for(int s=0;s<(1<<n);s++)
				for(int S=s^u;S;S=(S-1)&(s^u))
					if(f[i-1][s]!=f[0][0]&&D[s][S])
						f[i][s|S]=min(f[i][s|S],f[i-1][s]+D[s][S]*(i-1));
		for(int i=1;i<=n;i++)
			ans=min(ans,f[i][(1<<n)-1]);
	}
	cout<<ans;
	return 0;
}