解題區/解題區 - UVa

UVa 12701 - The Twin Head Dragon

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一棵樹，每次覆蓋不重疊的路徑，將路徑上的權重平均得到此次花費，目標覆蓋所有的邊，加總花費最小化。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
4
0 2 1
1 2 2
2 3 3
6
0 1 10000
0 2 10000
0 3 1
0 4 1
0 5 10000
0

Sample Output

1
2
3.5000
15001.5000

Solution

對於每一種狀態作紀錄，然後對於尚未使用過的邊作 bitmask，每次移除一條路徑上的結果。

// 後來發現似乎可以直接轉成有根樹，進行樹形 dp，真是失策。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
struct Edge {
    int to, w, i;
    Edge(int a = 0, int b = 0, int c = 0):
        to(a), w(b), i(c) {}
};
vector<Edge> g[16];
int n, used[1<<16];
double dp[1<<16];
double dfs(int);
void dfs2(int u, int mask, int w, int e, int o) {
    if (e) {
        dp[o] = min(dp[o], dfs(mask) + (double)w/e);
    }
    for (int i = 0; i < g[u].size(); i++) {
        if ((mask>>g[u][i].i)&1) {
            int v = g[u][i].to;
            dfs2(v, mask^(1<<g[u][i].i), w + g[u][i].w, e+1, o);
        }
    }
}
double dfs(int mask) {
    if (mask == 0)  return 0;
    if (used[mask]) return dp[mask];
    used[mask] = 1;
    double &ret = dp[mask];
    ret = 1e+30;
    for (int i = 0; i < n; i++) {
        dfs2(i, mask, 0, 0, mask);
    }
    return ret;
}
int main() {
    int x, y, w;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            g[i].clear();
        for (int i = 0; i < n - 1; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(Edge(y, w, i));
            g[y].push_back(Edge(x, w, i));
        }
        memset(used, 0, sizeof(used));
        printf("%.4lf\n", dfs((1<<(n-1)) - 1));
    }
    return 0;
}
/*
 4
 0 2 1
 1 2 2
 2 3 3
 6
 0 1 10000
 0 2 10000
 0 3 1
 0 4 1
 0 5 10000
 0 */