UVa 10911 - Forming Quiz Teams

  题目大意:给出2*n个点,将这些点配成n对,使得所有点对中两点的距离之和尽量小。

  用一个整数的二进制形式表示一个集合的子集,以每个集合为状态进行状态转移。具体参见《算法竞赛入门经典》9.5。

 #include <cstdio>
#include <cmath>
#include <algorithm>
#include <cfloat>
using namespace std; struct Point
{
int x, y;
} point[];
double dp[<<+]; double dis(int a, int b)
{
int x_diff = point[a].x - point[b].x;
int y_diff = point[a].y - point[b].y;
return sqrt(x_diff * x_diff + y_diff * y_diff);
} int main()
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
int n, kase = ;
char name[];
while (scanf("%d", &n) && n)
{
n *= ;
for (int i = ; i < n; i++)
scanf("%s%d%d", name, &point[i].x, &point[i].y);
dp[] = ;
for (int s = ; s < (<<n); s++)
{
dp[s] = DBL_MAX;
int p = ;
for ( ; p < n; p++)
if (s & (<<p)) break;
for (int i = p+; i < n; i++)
if (s & (<<i))
dp[s] = min(dp[s], dis(p, i)+dp[s^(<<p)^(<<i)]);
}
printf("Case %d: %.2lf\n", ++kase, dp[(<<n)-]);
}
return ;
}
上一篇:react-native学习资源


下一篇:使用Gitolite搭建轻量级的Git服务器