【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;
}