[NOIP2017]_D2T2 宝藏

广为Oier所知的状压题，就不提供链接了（其实还是我懒）

解法：

         奇(chao)妙(bu)玄(zheng)学(jing)的模拟退火算法

程序：

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read(){
	char c=getchar();int num=0;int f=1;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	return num*f;
}
inline void qwq(int x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
inline void write(int x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}
int n;
int maps[15][15];
int temp[15];int temp2[15];
int dep[15];

inline int dis(int a[]){
	memset(dep,0,sizeof(dep));
	dep[a[1]]=1;int re_value=0;
	rep(i,2,n){
		int tempx=INT_MAX;int xi=0;
		rep(j,1,n){
			if(a[i]==j)continue;
			if(maps[a[i]][j]!=INT_MAX&&dep[j]){
				if(maps[a[i]][j]*dep[j]<tempx){
					tempx=maps[a[i]][j]*dep[j];
					xi=j;
				}
			}
		}
		if(tempx==INT_MAX)return INT_MAX;
		re_value+=tempx;
		dep[a[i]]=dep[xi]+1;
	}
	return re_value;
}
inline bool O_K(double x,double y){
	if(x<=0)return true;
	return rand()<=exp((-x)/y)*RAND_MAX;
}
inline int solve(){
	double temper=1024;
	random_shuffle(temp+1,temp+n+1);
	rep(i,1,n){temp2[i]=temp[i];}
	int re_value=dis(temp);
	while(temper>0.01){
		int nop1=rand()%n+1;int nop2=rand()%n+1;
		swap(temp2[nop1],temp2[nop2]);
		int x=dis(temp2);int y=dis(temp);
		if(x==INT_MAX&&y==INT_MAX){
			swap(temp2[nop1],temp2[nop2]);
			temper*=0.99;
			continue;
		}
		re_value=min(re_value,min(x,y));
		if(O_K(x-y,temper)){
			swap(temp[nop1],temp[nop2]);
		}else{
			swap(temp2[nop1],temp2[nop2]);
		}
		temper*=0.99;
	}
	return re_value;
}
int main(){
	srand(time(NULL));
	n=read();int m=read();
	rep(i,1,n){
		rep(j,1,n){
			if(i==j)maps[i][j]=0;
			maps[i][j]=INT_MAX;
		}
		temp[i]=i;temp2[i]=i;
	}
	rep(i,1,m){
		int u=read();int v=read();int w=read();
		maps[u][v]=min(maps[u][v],w);
		maps[v][u]=maps[u][v];
	}
	
	int T=350;int ans=INT_MAX;
	while(T){
		T--;
		ans=min(ans,solve());
	}
	write(ans);
	return 0;
}

本程序不知为何，在UOJ上只有97，被Extra Test 7卡WA了

（欢迎大佬提供改进意见）