原题： HDU 3362 http://acm.hdu.edu.cn/showproblem.php?pid=3362
开始准备贪心搞，结果发现太难了，一直都没做出来。后来才知道要用状压DP。
题意：题目给出n(n <= 18)个点的二维坐标，并说明某些点是被固定了的，其余则没固定，要求添加一些边，使得还没被固定的点变成固定的，可见题目中的图形sample。
由于n很小，而且固定点的顺序没有限制，所以需要用状态压缩DP。
注意：
1.当一个没固定的点和两个固定了的点连接后，该点就被（间接）固定了（三角形的稳定性质）
2.被固定的点还可以用来固定别的点
因此，对于当前需要固定的点，在已经是固定状态的点中选出两个距离当前点最小的，这就保证了局部最优，从起始状态开始转移，最后判断能否到达最终目标状态就可以了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
using namespace std;
#define N 100007 struct Point
{
double x,y;
int f;
}p[];
double dp[<<];
int unfix[];
double dis[];
int n; double Dis(int i,int j)
{
Point ka = p[i];
Point kb = p[j];
return (double)sqrt((ka.x-kb.x)*(ka.x-kb.x)+(ka.y-kb.y)*(ka.y-kb.y));
} double Fixit(int state,int tofix)
{
int i = ,j;
int tmp = state;
memset(dis,,sizeof(dis));
while(i < n)
{
if(tmp & ) //已固定点
{
unfix[i] = ;
dis[i] = Dis(tofix,i);
}
else
unfix[i] = ;
i++;
tmp >>= ;
}
double mini_1 = Mod;
int tag = -;
for(i=;i<n;i++) //选第一个点
{
if(!unfix[i]) //fixed
{
if(dis[i] < mini_1)
{
mini_1 = dis[i];
tag = i;
}
}
}
double mini_2 = Mod;
for(i=;i<n;i++) //选第二个点
{
if(i == tag) //选过
continue;
if(!unfix[i])
{
if(dis[i] < mini_2)
mini_2 = dis[i];
}
}
if(mini_1+mini_2 >= Mod)
return -;
return mini_1+mini_2;
} int main()
{
int i,j;
int Na;
while(scanf("%d",&n)!=EOF && n)
{
int S = ;
Na = (<<n)-;
for(i=;i<n;i++)
{
scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].f);
if(p[i].f)
S |= (<<i);
}
for(i=;i<=Na;i++)
dp[i] = Mod;
dp[S] = ;
for(i=S;i<Na;i++)
{
if(dp[i] == Mod)
continue;
for(j=;j<n;j++) //选一个unfix的点固定
{
if(i & (<<j)) //已fix,跳过
continue;
double delta = Fixit(i,j);
if(delta == -)
continue;
else //更新固定完这个点后的最少花费
dp[i|(<<j)] = min(dp[i|(<<j)],dp[i]+delta);
}
}
if(dp[Na] == Mod)
puts("No Solution");
else
printf("%.6lf\n",dp[Na]);
}
return ;
}