题目大意：题目给出n(n <= 18)个点的二维坐标，并说明某些点是被固定了的，其余则没固定，要求添加一些边，使得还没被固定的点变成固定的，当一个没固定的点和两个固定了的点连接后，该点就被间接固定了（三角形的稳定性质），无论是直接固定还是间接固定的点，都可以供以后的点用于固定，添加的边的总长度即为代价

题解：观察数据范围，状压Dp可做，对于当前需要固定的点，在已经是固定状态的点中选出两个距离当前点最小的，这就保证了局部最优，从起始状态开始转移，最后判断能否到达最终目标状态就可以了。

#include <cstdio>#include <algorithm>#include <cmath>using namespace std;int n,x[20],y[20],fix[20];double dp[1<<18];double dis(int a,int b){    return sqrt(1.0*(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])*1.0);}double F(int pos,int x){    double ans=0,d[20];    bool mark[20];    for(int i=0;i<n;i++){        if((1<<i)&pos)mark[i]=1,d[i]=dis(i,x);        else mark[i]=0;    }    for(int i=0;i<2;i++){        double min=1e9;int p=0;        for(int j=0;j<n;j++)if(mark[j]&&d[j]<min)min=d[j],p=j;        ans+=min; mark[p]=0;    }if(ans>=1e9)return -1;    return ans;} int main(){    while(scanf("%d",&n),n){        int begin=0,end=0;        for(int i=0;i<n;i++){            scanf("%d%d%d",&x[i],&y[i],&fix[i]);            if(fix[i])begin+=(1<<i);            end+=(1<<i);        }        for(int i=0;i<(1<<n);i++)dp[i]=1e9;dp[begin]=0;        for(int i=begin;i<end;i++){            if(dp[i]==1e9)continue;            for(int j=0;j<n;j++){                if(i&(1<<j))continue;                double sum=F(i,j);                if(sum>0)dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+sum);            }        }        if(dp[end]==1e9)puts("No Solution");        else printf("%.6lf\n",dp[end]);    }return 0;}

HDU 3362 Fix