原题： 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[22]; double dp[1<<20]; int unfix[21]; double dis[20]; 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 = 0,j; int tmp = state; memset(dis,0,sizeof(dis)); while(i < n) { if(tmp & 1) //已固定点 { unfix[i] = 0; dis[i] = Dis(tofix,i); } else unfix[i] = 1; i++; tmp >>= 1; } double mini_1 = Mod; int tag = -1; for(i=0;i<n;i++) //选第一个点 { if(!unfix[i]) //fixed { if(dis[i] < mini_1) { mini_1 = dis[i]; tag = i; } } } double mini_2 = Mod; for(i=0;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 -1; return mini_1+mini_2; } int main() { int i,j; int Na; while(scanf("%d",&n)!=EOF && n) { int S = 0; Na = (1<<n)-1; for(i=0;i<n;i++) { scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].f); if(p[i].f) S |= (1<<i); } for(i=0;i<=Na;i++) dp[i] = Mod; dp[S] = 0; for(i=S;i<Na;i++) { if(dp[i] == Mod) continue; for(j=0;j<n;j++) //选一个unfix的点固定 { if(i & (1<<j)) //已fix,跳过 continue; double delta = Fixit(i,j); if(delta == -1) continue; else //更新固定完这个点后的最少花费 dp[i|(1<<j)] = min(dp[i|(1<<j)],dp[i]+delta); } } if(dp[Na] == Mod) puts("No Solution"); else printf("%.6lf\n",dp[Na]); } return 0; }
2014 Super Training #1 B Fix 状压DP,布布扣,bubuko.com
2014 Super Training #1 B Fix 状压DP
原文：http://www.cnblogs.com/whatbeg/p/3812714.html
