#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <time.h>
using namespace std;


#define N 100				//種群規模
#define M 80				//子代雜交的對數
#define GEN 5000			//種群遺傳代數
#define MAX 32767
int *son[2*M],sontotal[2*M];
int city,*dis;


int* savedata(FILE *fp)
{
	char temp;
	short int i,j,t;
	int *a,n;
	while(1)
	{
		fread(&temp,sizeof(char),1,fp);
		if(temp=='\n')break;
		city=city*10+atoi(&temp);
	}
	n=city*(city+1)/2;
	a=(int*)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
		a[i]=0;
	i=0;
	j=1;
	t=0;
	while(!feof(fp))
	{
		fread(&temp,sizeof(char),1,fp);
		if(temp==' ')
		{
			t++;
			if(t<j)i++;
			continue;
		}
		if(temp=='\n')
		{
			i++;
			j++;
			t=0;
			continue;
		}
		if(t>=j)continue;
		
		a[i]=a[i]*10+atoi(&temp);
	}
	return a;
}

/*	初始化種群 */
void RandInit(int*a[])
{
	short int i,j,k,u,v,tem;

	for(i=0;i<N;i++)
	{
		u=rand()%city;
		v=rand()%city;
		while(u==v)
			v=rand()%city;
		if(u>v)
		{
			tem=u;
			u=v;
			v=tem;
		}
		for(j=u,k=v;j<(u+v)/2.0+0.5;j++,k--)
		{
			tem=a[i][j];
			a[i][j]=a[i][k];
			a[i][k]=tem;
		}
	}
//	for (i=0;i<N;i++)
//		for(j=0;j<city;j++)
//			printf("%d ",a[i][j]);
//	printf("");
}

/* 計算每個個體的路程作為相應的適應值 */

void compdis(int* c[],int* t)
{
	int i,j,k,m,tem;
	for(i=0;i<N;i++)
	{
		t[i]=0;
		for(j=0;j<city;j++)
		{
			k=c[i][j];
			if (j==city-1) 
				m=c[i][0];
			else
				m=c[i][j+1];
			if(k>m)
				tem=k*(k+1)/2+m;
			else
				tem=m*(m+1)/2+k;
			t[i]+=dis[tem];
		}
			
	}
}

/* 計算每個個體的繁殖概率p[i] */

void comprate(int *t,float *p)
{
	int maxdis,i;

	for(i=0;i<N;i++)
		if(t[i]>maxdis)
			maxdis=t[i];
	for(i=0;i<N;i++)
		p[i]=t[i]*1.0/maxdis;

}

/* 
	兩個個體進行雜交
	隨機取A(B)中一段區域插入到B(A)前面,刪除其后重復的城市編號
 */

void cross(int *cir[],int i,int k,int m)
{
	short int u,v,tem,j,t,r;

	u=rand()%city;
	v=rand()%city;
	while(u==v)
		v=rand()%city;
	if(u>v)
	{
		tem=u;
		u=v;
		v=tem;
	}
	for(j=0;j<city;j++){
		son[i][j]=cir[m][j];
		son[i+M][j]=cir[k][j];
	}
// 	for(j=0;j<city;j++)
// 	printf("%d ",son[i+M][j]);
// 	printf("\n");
// 	for(j=0;j<city;j++)
// 	printf("%d ",son[i][j]);
// 	printf("\n");

	
	for(j=city-1;j>=0;j--)					
		for(t=u;t<=v;t++)
			if(son[i][j]==cir[k][t]){
				for(r=j;r>0;r--)
					son[i][r]=son[i][r-1];
				son[i][r]=-1;
				j++;
				break;
			}
	for(j=0;j<v-u+1;j++)
		son[i][j]=cir[k][u+j];

// 	for(j=0;j<city;j++)
// 	printf("%d ",son[i][j]);
//  	printf("\n");

	u=rand()%city;
	v=rand()%city;
	while(u==v)
		v=rand()%city;
	if(u>v)
	{
		tem=u;
		u=v;
		v=tem;
	}
	for(j=city-1;j>=0;j--)					
	for(t=u;t<=v;t++)
		if(son[i+M][j]==cir[m][t]){
			for(r=j;r>0;r--)
				son[i+M][r]=son[i+M][r-1];
			son[i+M][r]=-1;
			j++;
			break;
		}
	for(j=0;j<v-u+1;j++)
		son[i+M][j]=cir[m][u+j];

// 	for(j=0;j<city;j++)
// 	printf("%d ",son[i+M][j]);
//  	printf("\n");
}

/* 
	變異函數 
	隨機產生兩個點，直接進行交換，迭代50次
*/

void mutation(int i)
{
	int k=0;
	int u,v,tem;
	
	while(k<50)
	{
		u=rand()%city;
		v=rand()%city;
		while(u==v)
			v=rand()%city;
//		for(j=0;j<city;j++)
//			printf("%d",son[i][j]);
		tem=son[i][u];
		son[i][u]=son[i][v];
		son[i][v]=tem;
//				for(j=0;j<city;j++)
// 			printf("%d",son[i][j]);
		u=rand()%city;
		v=rand()%city;
		while(u==v)
			v=rand()%city;
		//		for(j=0;j<city;j++)
		//			printf("%d",son[i][j]);
		tem=son[i+M][u];
		son[i+M][u]=son[i+M][v];
		son[i+M][v]=tem;
		k++;
	}

}

/************************************************************************/
/* 更新種群                                                             */
/************************************************************************/

void selectgen(int *cir[],int *total)
{
	short int father[N],f=0,genarate[N],s=0;
	short int i,j,k,u,v,j1,j2;
	int minf,mins;
	for (i=0;i<N;i++) {
		minf=10*MAX;
		mins=10*MAX;
		for (j=0;j<N;j++)
			if(total[j]<minf)
			{	
				j1=j;
				minf=total[j];
			}
// 			printf("");
// 			printf("");
		for(j=0;j<2*M;j++)
			if(sontotal[j]<mins)
			{
				j2=j;
				mins=sontotal[j];
			}
// 			printf("");
// 			printf("");
		if(minf<=mins){
			father[f]=j1;
			total[j1]=total[j1]+MAX;
			f++;
		}			
		else{
			genarate[s]=j2;
			sontotal[j2]=sontotal[j2]+MAX;
			s++;
		}
	}
	sort(father,father+f);
	j=0;
	k=0;
	for (i=0;i<N;i++) {
		if(i==father[j]&&j<f){
			j++;
			continue;
		}
		else{
			u=genarate[k];
			k++;
			total[i]=sontotal[u];
			for(v=0;v<city;v++)
				cir[i][v]=son[u][v];
		}
	}
	for(i=0;i<N;i++)
		total[i]=total[i]-MAX;
// 	for(i=0;i<N;i++)
// 		printf("%d ",total[i]);
	
}

int main()
{
	int *cir[N],total[N],temp[N],m,min;
	float p[N],pc,pm;
	short int i,j,k,u,v,gen=0,tem;
	FILE* fp;
	clock_t start,finish;

	start=clock();

	fp = fopen("disCHN144.txt","r");
	dis=savedata(fp);

	for(i=0;i<N;i++)
		cir[i]=(int*)malloc(city*sizeof(int));		//最后要釋放
	for(i=0;i<2*M;i++)
		son[i]=(int*)malloc(city*sizeof(int));		//最后要釋放	

	srand((unsigned int)time(NULL));
	for(i=0;i<N;i++)
		for(j=0;j<city;j++)
			cir[i][j]=j;
	RandInit(cir);						//初始化種群

	while(gen<GEN)
	{
		compdis(cir,total);					//計算每個個體的適應值－－路程，在這里適應值越小越適應
		comprate(total,p);					//計算每個個體的繁殖概率p[i]
	
		m=0;
		k=0;

		pc=rand()%10000/10000.0;
		for(i=0;i<N;i++)
			if(p[i]>pc)					//temp[k]存放繁殖概率大于pc的個體編號,這些個體是準備雜交的個體
			{
				temp[k]=i;
				k++;
			}
		while(m<M)
		{
			u=rand()%k;
			v=rand()%k;
			while(u==v)
				v=rand()%k;
			i=temp[u];						//k,m是準備雜交的兩個個體
			j=temp[v];
			cross(cir,m,i,j);
			pm=rand()%10000/10000.0;
			if(0.01>pm)						//變異概率為1%
				mutation(m);				
			m++;
		}
		for (i=0;i<2*M;i++)					//.................................
		{	sontotal[i]=0;
			for(j=0;j<city;j++)
			{
				k=son[i][j];
				if (j==city-1) 
					m=son[i][0];
				else
					m=son[i][j+1];
				if(k>m)
					tem=k*(k+1)/2+m;
				else
					tem=m*(m+1)/2+k;
				sontotal[i]+=dis[tem];
			}
/*			printf("%d ",sontotal[i]);*/
		}
// 		for (i=0;i<2*M;i++) 
// 			printf("%d ",sontotal[i]);
		selectgen(cir,total);						//在2M+N個體中選擇N個最優個體作為下一代種群
		gen++;
	}
	min=10*MAX;
	for (i=0;i<N;i++)	
		if(total[i]<min)
		{
			min=total[i];
			j=i;
		}
	printf("%d\n",min);
	for (i=0;i<city;i++)
		if(i==city-1)
			printf("%d\n",cir[j][i]);
		else
			printf("%d->",cir[j][i]);
	for(i=0;i<N;i++)
		free(cir[i]);		
	for(i=0;i<2*M;i++)
		free(son[i]);		
/*	free(dis);*/
	finish=clock();
	printf("%.3f(s)\n",(finish-start)/1000.0);
	return 0;
}