小白书上讲的很详细
n对点 两两配对 求每对点的距离之和最小
状态压缩DP 经典
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 18;
double dp[1<<maxn];
double x[maxn];
double y[maxn];
double d(int i, int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
int cas = 1;
int n;
while(scanf("%d", &n) && n)
{
n *= 2;
for(int i = 0; i < n; i++)
{
char s[100];
scanf("%s %lf %lf", s, &x[i], &y[i]);
}
dp[0] = 0;
for(int s = 1; s < (1<<n); s++)
{
int i, j;
dp[s] = 0x7fffffff;
for(i = 0; i < n; i++)
if(s&(1<<i))
break;
for(int j = i+1; j < n; j++)
{
if(s&(1<<j))
{
dp[s] = min(dp[s], dp[s^(1<<i)^(1<<j)]+d(i, j));
}
}
}
printf("Case %d: %.2lf\n", cas++, dp[(1<<n)-1]);
}
return 0;
}
/*
5
sohel 10 10
mahmud 20 10
sanny 5 5
prince 1 1
per 120 3
mf 6 6
kugel 50 60
joey 3 24
limon 6 9
manzoor 0 0
1
derek 9 9
jimmy 10 10
*/
UVa 10911 Forming Quiz Teams / 状态压缩DP,布布扣,bubuko.com
UVa 10911 Forming Quiz Teams / 状态压缩DP
原文：http://blog.csdn.net/u011686226/article/details/21083241