后端 uva 12701 - the twin head dragon

wanana · June 11, 2020 · 5 hits

contents

Problem

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

Sample Input

1234567891011
40 2 11 2 22 3 360 1 100000 2 100000 3 10 4 10 5 100000

Sample Output

12
3.500015001.5000

Solution

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

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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
#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("%.4lfn", 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 */
No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.