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 ;
 }