【NOIP2017】宝藏【状态压缩】【回溯】

传送门

一年前觉得这道题简直是看都不可以看的神题。

现在想想好像简单的很。

找一个最小生成树，边权规则和根节点距离有关。

首先肯定有个枚举根节点的操作。

然后看一看12的范围状态压缩先。目标是所有点都进入联通块，那直接搜索一下。

边数也就72条不到，好像也没啥影响，，怎么乱搞都能过的鸭子。

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int n,m;
int g[15][15];
int f[1<<13],dis[15];int ans=0x3f3f3f3f;;
void dfs(int u){
	for(int i=1;i<=n;i++){
		if(1<<(i-1)&u){
			for(int j=1;j<=n;j++){
				if(g[i][j]<1000000&&!(1<<(j-1)&u)){
					if(f[u|(1<<(j-1))]>f[u]+dis[i]*g[i][j]){
						f[u|(1<<(j-1))]=f[u]+dis[i]*g[i][j];
						int now=dis[j];
						dis[j]=dis[i]+1;
						dfs(u|(1<<(j-1)));
						dis[j]=now;
					}
				}
			}
		}
	}
}
signed main(){
	n=in;m=in;memset(g,10,sizeof(g));
	for(int i=1;i<=m;i++){
		int a=in;int b=in;int c=in;
		g[a][b]=min(g[a][b],c);
		g[b][a]=min(g[b][a],c);
	}
	for(int i=1;i<=n;i++){
		memset(f,10,sizeof(f));
		memset(dis,10,sizeof(g));
		dis[i]=1;f[1<<(i-1)]=0;
		dfs(1<<(i-1));
		ans=min(ans,f[(1<<n)-1]);
	}
	cout<<ans;
	return 0;
}