[NOIp提高组2017]宝藏

解题思路

初识模拟退火，于是拿这道题练练手

我们指定没有连边的结点连了一条权值为inf的边，成为完全图，避免了不存在的生成树

这样枚举根，然后每一次枚举都跑若干遍模拟退火

初始状态就是一张菊花图，父亲都指向当前为根的结点

每次产生相近解只需要随机改变一个结点的父亲，但是这样并不能保证产生的关系任然是一棵树

考虑到最多只有12个结点，每次跑一遍并查集暴力判断，可以归结到常数复杂度

多试几个种子就过了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>

int n,m,x,y,v;
long long M[20][20];
const long long inf=0x3f3f3f3f3f3f;
int Fa[20];

namespace SA{
	const double start_T=10000;
	const double delta_T=0.993;
	const double low_T=1e-12;

	long long calc(int now,int fa,int dep){
		long long ret=dep*M[fa][now];
		for (int i=1;i<=n;i++){
			if (Fa[i]!=now||i==Fa[i]) continue;
			ret+=calc(i,now,dep+1);
		}
		return ret;
	}

	namespace MFS{
		int B[20];
		inline void init(){for (int i=1;i<=n;i++) B[i]=i;}
		inline int find(int k){return (k==B[k])?(k):(B[k]=find(B[k]));}
		void merge(int a,int b){
			int fa=find(a),fb=find(b);
			if (fa==fb) return;
			B[fa]=fb;
		}
		inline bool same(int a,int b){return find(a)==find(b);}
	}

	bool allowed(){
		MFS::init();
		for (int i=1;i<=n;i++){
			if (i!=Fa[i]&&MFS::same(i,Fa[i])) return false;
			MFS::merge(i,Fa[i]);
		}
		return true;
	}

	long long ans;

	inline double rand_double(){return rand()/(double)RAND_MAX;}

	long long SA_main(int root){
		ans=calc(root,0,0);
		double T=start_T;
		while (T>low_T){
			int change,to;
			do{
				change=rand()%n+1,to=rand()%n+1;
			}while (change==to||change==root);
			int ec=Fa[change];
			Fa[change]=to;
			if (!allowed()){
				Fa[change]=ec;
				continue;
			}
			long long nxt=calc(root,0,0);
			if (nxt<ans||exp((ans-nxt)/T)>rand_double()) ans=nxt;
			else Fa[change]=ec;
			T*=delta_T;
		}
		return ans;
	}
}

long long Ans=inf;

int main(){
    srand(/**/);//种子被和谐了
	scanf("%d%d",&n,&m);
	if (n==1){printf("%d
",0);return 0;}
	memset(M,0x3f,sizeof(M));
	for (int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&v);
		M[x][y]=M[y][x]=std::min(M[x][y],(long long)v);
	}
	for (int i=0;i<=n;i++)
		for (int j=0;j<=n;j++)
			M[i][j]=std::min(M[i][j],inf);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++) Fa[j]=i;//初始状态菊花图
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));
		Ans=std::min(Ans,SA::SA_main(i));//这里多做几次
	}
	printf("%lld
",Ans);
}