模拟退火 90pts 求调

#include<bits/stdc++.h>
using namespace std;
const double st=1145,ed=1e-15,down=0.998;
const int N=37;
int ans[N],n,m,e[N][N],a,b,p[N],tot=1e9;

int get(){
	int res=0;
	for(int i=1;i<=n/2;++i)
		for(int j=n/2+1;j<=n;++j)
			if(e[p[i]][p[j]])
				++res;
	return res;
}

void SA(){
	double t=st;
	while(t>ed){
		int x=rand()%(n/2)+1;
		int y=rand()%(n/2)+1+n/2;
		swap(p[x],p[y]);
		int now=get();
		if(now<tot){
			tot=now;
			for(int i=1;i<=n;++i)
				ans[i]=p[i];
		}
		else{
			if(exp((tot-now)/t)<double(rand())/RAND_MAX)
				swap(p[x],p[y]);
		}
		t*=down;
	}
}

int main(){
	srand(time(0));
	cin>>n>>m;
	for(int i=1;i<=m;++i)
		cin>>a>>b,
		e[a][b]=e[b][a]=1;
	for(int i=1;i<=n;++i)
		p[i]=i;
	tot=get();
	for(int i=1;i<=30;++i)
		SA();
	sort(ans+1,ans+1+n/2);
	for(int i=1;i<=n/2;++i)
		cout<<ans[i]<<" ";
	return 0;
}