记录编号	119106	评测结果	AAAATTTTTA
题目名称	线型网络	最终得分	50
用户昵称	cstdio	是否通过	未通过
代码语言	C++	运行时间	8.633 s
提交时间	2014-09-11 11:32:19	内存使用	1.06 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define sqr(x) (x)*(x)
const int SIZEN=21,SIZEP=4050;
const double INF=1e9;
int N;
double x[SIZEN]={0},y[SIZEN]={0};
double dist(int a,int b){
	return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));
}
int bigrand(void){
	return ((rand()<<15)|rand())&0x7fffffff;
}
int random(int x,int y){
	return bigrand()%(y-x+1)+x;
}
void random_permute(int *s){
	for(int i=1;i<=N;i++) s[i]=i;
	for(int i=1;i<=N;i++) swap(s[i],s[random(i,N)]);
}
class CYCLE{
public:
	int s[SIZEN];
	double len;//长度
	void calc_len(void){
		len=0;
		for(int i=1;i<N;i++) len+=dist(s[i],s[i+1]);
	}
	void mutation(void){//变异
		int i=random(1,N);
		int j=random(i,N);
		while(i<j){
			swap(s[i],s[j]);
			i++,j--;
		}
	}
	void mating(CYCLE &b,int l,int r){//b送给它一段祖传的染色体......
		int atp[SIZEN]={0};
		for(int i=1;i<=N;i++) atp[s[i]]=i;
		for(int i=l;i<=r;i++){
			if(s[i]!=b.s[i]){
				atp[s[i]]=atp[b.s[i]];
				swap(s[i],s[atp[b.s[i]]]);
				atp[b.s[i]]=i;
			}
		}
	}
};
int P=400;
CYCLE A[SIZEP],B[SIZEP];
CYCLE ans;
double f[SIZEP]={0};
void select(void){//自然选择,把B选到A,此时B已经计算出了len
	double mx=0;
	for(int i=1;i<=P;i++) mx=max(mx,B[i].len);
	double sum=0;
	for(int i=1;i<=P;i++) f[i]=mx*1000.0/B[i].len,sum+=f[i];
	int tot=0;
	for(int i=1;i<=P;i++){
		int tmp=(f[i]/sum)*(P+0.0)+0.5;
		while(++tot<=N&&tmp--) A[tot]=B[i];
	}
}
void multiply(void){//繁殖,把A繁殖到B,并计算B的len,用它更新答案
	double mxl=INF;int mxid;
	for(int i=1;i<=P;i++){
		if(A[i].len<mxl) mxl=A[i].len,mxid=i;
		B[i]=A[i];
	}
	for(int i=1;i<P;i+=2){//梅亭,不对,mating
		int l=random(1,N),r=random(l,N);
		B[i].mating(A[i+1],l,r);
		B[i+1].mating(A[i],l,r);
	}
	int vp=10;//变异概率的倒数
	for(int i=1;i<=P;i++) if(random(1,vp)==1) B[i].mutation();//变异
	for(int i=1;i<=P;i++){//更新答案
		B[i].calc_len();
		if(B[i].len<ans.len) ans=B[i];
	}
	for(int i=1;i<=P;i++) if(A[i].len<B[i].len) B[i]=A[i];//子比父强优化
	if(A[mxid].len<B[mxid].len) B[mxid]=A[mxid];//精英主义优化
	//B[1]=mx;
}
void GA(void){//遗传算法
	int gtot=10000;//传代次数
	ans.len=INF;
	for(int i=1;i<=P;i++){
		random_permute(A[i].s);
		A[i].calc_len();
		if(A[i].len<ans.len) ans=A[i];
	}
	for(int i=1;i<=gtot;i++){
		multiply();
		select();
	}
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lf%lf",&x[i],&y[i]);
}
int main(void){
	freopen("linec.in","r",stdin);
	freopen("linec.out","w",stdout);
	//srand(time(0));
	read();
	GA();
	printf("%.2lf\n",ans.len);
	return 0;
}