描述 Description

一个平面内有N个点，你的任务是将这N个点配对（N为偶数，且<=20），使得每一个点恰好在一个配对中，所有点对中两点距离之和最小。

输入格式 InputFormat

第一行n
接下来的n行，每行两个整数，表示横纵坐标

输出格式 OutputFormat

一个数，所有点对中两点距离之和最小值 精确到小数点后两位

样例输入 SampleInput [复制数据]

4

1 1

1 2

100 1

100 2

样例输出 SampleOutput [复制数据]

2.00

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<string>

#include<algorithm>

using namespace std;

#define SIZE 22

#define INF 99999999

float p[SIZE][2];

float dist[SIZE][SIZE];

double ans=INF;

int tag[SIZE];

int N;

int search(int depth,double s)

{

if(2*depth==N)

{

if(s<ans) ans=s;

return 0;

}

int i,node;

double tmp;

for(i=0;i<N;i++)

if(!tag[i])

{

node=i;

break;

}

tag[node]=1;

for(;i<N;i++)

if(!tag[i] && (tmp=s+dist[node][i])<ans)

{

tag[i]=1;

search(depth+1,tmp);

tag[i]=0;

}

tag[node]=0;

return 0;

}

int main(void)

{

int i,j;

double dx,dy;

scanf("%d",&N);

for(i=0;i<=N;i++)

scanf("%f%f",p[i],p[i]+1);

for(i=0;i<N;i++)

for(j=i+1;j<N;j++)

{

dx=p[i][0]-p[j][0];

dy=p[i][1]-p[j][1];

dist[i][j]=sqrt(dx*dx+dy*dy);

}

search(0,0);

printf("%.2lf",ans);

return 0;

}

tyvj 1169