程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5148 Cities

HDU 5148 Cities

編輯：關於C++

題意：

n（2000）個點的樹從中選出k（50）個點要求選出的點中等概率選出兩個點使得這兩點的期望值最小輸出期望值乘k^2

思路：

我們將題目的要求化簡 sum( sum( dis(i,j) ) ) / k^2 * k^2 其實就是求 sum( sum( dis(i,j) ) ) 其中i和j為任意選出的k個點

設dp[i][k]表示掃描完i為根的子樹選出k個點的最小sum

那麼轉移方程就是 dp[father][k1+k2] = min( dp[father][k1]+dp[son][k2]+edge*k2*(k-k2)*2 ) 這個方程很好理解注意式中的k2 我們利用它計算的原因是 son樹內之選k2個點

代碼書寫的時候還要注意 dp過程中k1需要倒著for 這個做過01背包應該很好理解

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define N 2010
#define M 60

inline void scand(int &ret) {
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9')
        ;
    while (c >= '0' && c <= '9')
        ret = ret * 10 + (c - '0'), c = getchar();
}

int t, n, m;
LL dp[N][M];
LL ans;
int head[N], tot;

struct edge {
    int v, w, next;
} ed[N * 2];

void add(int u, int v, int w) {
    ed[tot].v = v;
    ed[tot].w = w;
    ed[tot].next = head[u];
    head[u] = tot++;
}

void update(LL &x, LL y) {
    if (y == -1) return;
    if (x == -1 || x > y) x = y;
}

void dfs(int u, int fa) {
    dp[u][1] = 0;
    for (int i = head[u]; ~i; i = ed[i].next) {
        int v = ed[i].v;
        if (v != fa) {
            dfs(v, u);
            LL w = ed[i].w;
            for (int k1 = m - 1; k1; k1--) {
                if (dp[u][k1] == -1) continue;
                for (int k2 = 1; k2 < m; k2++) {
                    if (k2 + k1 > m || dp[v][k2] == -1) break;
                    update(dp[u][k1 + k2], dp[u][k1] + dp[v][k2] + w * (m - k2) * k2 * 2);
                }
            }
        }
    }
    update(ans, dp[u][m]);
}

int main() {
    scand(t);
    while (t--) {
        scand(n);
        scand(m);
        memset(head, -1, sizeof (head));
        tot = 0;
        for (int i = 2; i <= n; i++) {
            int u, v, w;
            scand(u);
            scand(v);
            scand(w);
            add(u, v, w);
            add(v, u, w);
        }
        memset(dp, -1, sizeof (dp));
        ans = -1;
        dfs(1, 0);
        printf("%I64d\n", ans);
    }
    return 0;
}