Problem Solving►UVa

UVa 10911 - Forming Quiz Teams

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

利用二進位存集合，狀態壓縮。(1:要配對的)

從小到大窮舉子集，bottom-up: for (int s = 1; s < (1 << n); s++)

接著從子集中找出要配對的第一個點:

for (i = n - 1; i >= 0; i--)//最前面的元素，也就是要配對的(向右尋找)
    if (s&(1 << i))
        break;

再從它之後的找一點配對:

for (int j = 0; j < i; j++)//窮舉 i 右邊的元素來配對
    if (s&(1 << j))
        dp[s] = MIN(dp[s], dis[j][i] + dp[s ^ (1 << i) ^ (1 << j)]);

s ^ (1 << i) ^ (1 << j) 也就是 i , j 這兩點還未配對時的集合狀態，其 dp[] 就是那時的最短距離。

Code

UVa 10911
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cmath>
#define MIN(a,b) ((a)<(b)?(a):(b))

struct Student
{
    int x, y;
    double getDis(Student& p)
    {
        return sqrt((x - p.x)*(x - p.x) + (y - p.y)*(y - p.y));
    }

}student[16];

int main()
{
    int n, i, Case = 1;
    double dp[1 << 16], dis[16][16];

    while (scanf("%d", &n) && n)
    {
        n <<= 1;
        for (i = 0; i < n; i++)
            scanf("%*s%d%d", &student[i].x, &student[i].y);

        for (i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                dis[i][j] = student[i].getDis(student[j]);

        dp[0] = 0;
        //s = set of student, 二進位集合
        for (int s = 1; s < (1 << n); s++) 
        {
            dp[s] = 1e9;
            for (i = n - 1; i >= 0; i--)//最前面的元素，也就是要配對的
                if (s&(1 << i))
                    break;

            for (int j = 0; j < i; j++)//窮舉 i 右邊的元素來配對
                if (s&(1 << j))
                    dp[s] = MIN(dp[s], dis[j][i] + dp[s ^ (1 << i) ^ (1 << j)]);
        }

        printf("Case %d: %.2lf\n", Case++, dp[(1 << n) - 1]);
    }

    return 0;
}