题目

题目描述

背景：“$10$月$6$日那天，电脑组组织了博饼活动，博饼结束后碗和骰子就放在了机房
结果喜感的翔霸整天有事没事地就跑去玩那骰子，搞得叮当叮当响的
终于有一天，翔霸再次去玩那些骰子的时候，曾大实在受不了了，就跟翔霸比赛博饼，如果翔霸输了，以后就不能在机房博饼
当然了，翔霸那么神，怎么可能输呢？哈哈
翔霸在赢得了跟曾大的比赛后，为了庆祝以后能在机房继续玩那些骰子，决定组织大家博饼
由于受到涛霸和学霸比赛谁先博到状元这个游戏的启发，翔霸也准备组织一个类似的比赛，他在电脑组里面选出$2\times n$个人，分成$n$组，一组$2$人，比赛谁先博到状元
作为每组幸运成为状元王中王那个人的奖励，翔霸将会教他神奇的翔状数组
但是平常大家都很忙的，所以只能在周末组织了
电脑组里每个神犇的家都很神奇地能用坐标$(x,y)$表示，两两神犇的家的距离定义为两个点之间的直线距离，被分为同一组的两个神犇商量其中一个人到另一个人家里去比赛
电脑组里的神犇都希望自己能到离自己家尽量近的人家里去比赛
作为组织者的翔霸想知道，如何分组才能让每组里要走到另一个人家里去博饼的人走的路径的和最小（保留两位小数）？
因为翔霸比较神，所以可能会组织好多次比赛，但具体组织多少次比赛要看翔霸的心情，因此翔霸决定当他选$0$个人的时候表示他不准备组织比赛了

输入格式

输入包含多组数据，当$n$为$0$时表示输入结束
对于每组数据：
第一行一个正整数$n$
第$i+1$行$2$个正整数，表示每个人的坐标$x_i,y_i$

输出格式

对于每组数据：
仅一行，表示最优分组方案下的路径和

样例

样例输入

5
zx 10 10
lx 20 10
xy 5 5
hta 1 1
zkc 120 3
cxy 6 6
fz 50 60
cyx 3 24
lht 6 9
lyq 0 0
1
taoba 9 9
xueba 10 10
0

样例输出

118.40
1.41

数据范围与提示

$n\leqslant 8且n\in N^*$
$0\leqslant x,y\leqslant 1000$

题解

~~这题目背景是真的长~~
看一下数据范围：$n\leqslant 8且n\in N^*$，显然就是状压
假设状态$s$表示哪些人参加了博饼，$f_s$表示这些人参加博饼时，最短的距离
状态转移时就直接暴力枚举两个人作为一对（记得要是包含在状态$s$中的），答案就是这两个人的距离加上去掉这两个人以后的剩下的人最短距离
附上代码：

#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct ppap
{
    int x,y;
}h[20];
int n,m;
double f[65540];
char name[10];
double dis(int a,int b)
{     
    return sqrt((double)(h[a].x-h[b].x)*(h[a].x-h[b].x)+(double)(h[a].y-h[b].y)*(h[a].y-h[b].y));
}
double dfs(int step)
{
    if(f[step]!=1e9) return f[step];
    for(int i=0;i<m;i++) if(step&(1<<i)) for(int j=i+1;j<m;j++) if(step&(1<<j))
        f[step]=min(f[step],dfs(step-(1<<j)-(1<<i))+dis(i+1,j+1));
    return f[step];
}
int main()
{
    while(1){
        scanf("%d",&n),m=n*2;
        if(!n) break;
        for(int i=1;i<=m;i++) scanf(" %s%d%d",name,&h[i].x,&h[i].y);
        for(int i=1;i<(1<<m);i++) f[i]=1e9;
        printf("%.2lf\n",dfs((1<<m)-1));
    }
}