hdu 4003 Find Metal Mineral (樹形背包dp)

本文出自   http://blog.csdn.net/shuangde800

題目連結:  hdu-4003 

題意

    給一棵n個節點的樹, 節點編号為1~n, 每條邊都有一個花費值. 

    有k個機器人從S點出發, 問讓機器人周遊所有邊,最少花費值多少?

思路

    很好的一題, 推薦!

    前天看的這題, 今天才想出來的. 方法想出來後,代碼很簡單

    最近做的幾道dp,都是一開始沒什麼想法,然後過兩天再想就想出來了,也許是因為人的潛意識其實會一直在想某個問題

    翻看一下網上其他人的做法, 和我的稍有不同, 他們是用f(i, j)表示子樹i用j個機器人的最少花費, 一開始我也是這樣

    去想,但是沒想到怎麼去狀态轉移.

    然後我換了一種思路,很快就想出來了

    如果從根節點出發,周遊所有節點之後再回到原點, 那麼最少的花費一定是所有邊的權值之和sum的兩倍, 因為每條邊都走了兩次.

    而這題, 周遊完之後,并不需要走回出發點, 是以, 有些邊隻走了一次就可以了,

    如果用1台機器人走, 最少的的花費 = sum * 2 - {根節點到葉子節點路徑的最大權值和}

    如果是j台機器走, 我們要讓j台機器人隻走一次的邊的權值之和盡量大, 也就是減少的花費盡量大.

    那麼, 我的狀态表示為:

    f(i, j) 表示子樹i用j個機器人最多可以減少的花費.

    對于i節點, 它的每個子節點的子樹是一組物品, 我們可以選擇派1,2,...j個機器人走去

    需要注意, 如果派x個機器人走向某個子節點v, 那麼邊edge(i, v)就會被走了x次, 花費了x*w(i, v).

    而原始的sum中每條邊隻走了兩次, 是以走edge(i, v)的花費減少了 2*w(i,v) - x*w(i,v)

    最後可以得到狀态轉移式:

    f(i, j) = max{ max{f(i, j-k) + f(v, k) + 2*w(i,v) - k*w(i,v) | 1<=k<=j }  | v是i的兒子節點 }

    最終答案ans = sum * 2 - f(s, k)

代碼 

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : hdu-4003 Find Metal Mineral
 *   @description : 樹形背包dp
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/08/21 16:21 All rights reserved. 
 *======================================================*/
#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
         #include 
        
          #include 
         
           #define MP make_pair using namespace std; typedef pair
          
           PII; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 10010; namespace Adj { int size, head[MAXN]; struct Node{ int v, next, w; }E[MAXN*2]; inline void initAdj() { size = 0; memset(head, -1, sizeof(head)); } inline void addEdge(int u, int v, int w) { E[size].v = v; E[size].w = w; E[size].next = head[u]; head[u] = size++; } } using namespace Adj; // vector
           
            adj[MAXN]; int f[MAXN][12]; bool vis[MAXN]; int n, m, k; void dfs(int u) { vis[u] = true; for (int e = head[u]; e != -1; e = E[e].next) { int v = E[e].v; int w = E[e].w; if (vis[v]) continue; dfs(v); for (int i = k; i >= 1; --i) { for (int j = 1; j <= i; ++j) f[u][i] = max(f[u][i], f[u][i-j] + f[v][j] + 2*w - j*w); } } } int main(){ while (~scanf("%d%d%d", &n, &m, &k)) { initAdj(); int sum = 0; for (int i = 0; i < n - 1; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); sum += w; addEdge(u, v, w); addEdge(v, u, w); } memset(f, 0, sizeof(f)); memset(vis, 0, sizeof(vis)); dfs(m); printf("%d\n", sum * 2 - f[m][k]); } return 0; }