程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved