poj 1155 TELE （樹形背包dp）

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

題目連結： poj-1155

題意

       某收費有線電視網計劃轉播一場重要的足球比賽。他們的轉播網和使用者終端構成一棵樹狀結構，這棵樹的根結點位于足球比賽的現場，樹葉為各個使用者終端，其他中轉站為該樹的内部節點。

       從轉播站到轉播站以及從轉播站到所有使用者終端的信号傳輸費用都是已知的，一場轉播的總費用等于傳輸信号的費用總和。

    現在每個使用者都準備了一筆費用想觀看這場精彩的足球比賽，有線電視網有權決定給哪些使用者提供信号而不給哪些使用者提供信号。

    寫一個程式找出一個方案使得有線電視網在不虧本的情況下使觀看轉播的使用者盡可能多。

思路

樹形背包的入門題。

f(i, j)，表示子樹i轉播給j個使用者的最大收益值

這題可以看作是樹上的分組背包，每個子樹看作是一組物品，這一組物品可以取1個，2個...j個

然後就是套用分組背包的算法了

f(i, 1) = w(i), 當點i是葉子節點時

f(i, j) = max{ f(i, j-k) + f[v][k] - w(i, v) | v是i的兒子節點， 0<=k<=j}

代碼

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source：poj-1155 TELE
 *   @type: 樹形背包dp
 *   @author: shuangde
 *   @blog: blog.csdn.net/shuangde800
 *   @email: [email protected]
 *   Copyright (C) 2013/08/18 19:29 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 double PI = acos(-1.0); const int MAXN = 3010; namespace Adj{ int size, head[MAXN]; struct Node {int v, next, w; }E[MAXN]; void initAdj() { size = 0; memset(head, -1, sizeof(head)); } 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; / int n, m; int val[MAXN]; int f[MAXN][MAXN]; // 傳回的是有幾個葉子節點 int dfs(int u) { // init for (int i = 1; i <= m; ++i) f[u][i] = -INF; if (head[u] == -1) { f[u][1] = val[u]; return 1; } int sum = 0; for (int e = head[u]; e != -1; e = E[e].next) { int v = E[e].v, w = E[e].w; int numLeaf = dfs(v); sum += numLeaf; // 做分組背包 for (int s = sum; s >= 1; --s) { for (int k = 0; k <= numLeaf && k <= s; ++k) f[u][s] = max(f[u][s], f[u][s-k] + f[v][k] + w); } } return sum; } int main(){ while (~scanf("%d%d", &n, &m)) { initAdj(); for (int i = 1; i <= n - m; ++i) { int x, v, w; scanf("%d", &x); while (x--) { scanf("%d%d", &v, &w); addEdge(i, v, -w); } } for (int i = n - m + 1; i <= n; ++i) { scanf("%d", &val[i]); } dfs(1); for (int i = m; i >= 0; --i) { if (f[1][i] >= 0) { printf("%d\n", i); break; } } } return 0; }