题解 P1273 【有线电视网】

· · 题解

做过树上背包的同学应该会觉得这题比较简单，不过如果是没有做过的同学的话可能就...（比如我）

首先给大家推荐一道树上背包入门题：poj2486 以及讲解：qwq

那么这道题怎么做呢？

我一开始想的是先贪心处理收入大于花费的子树，然后用f[i][j]表示编号为i的节点所代表的子树在花费为j时能够开通的最多的用户数目。然后发现第二维不知道范围，连数组开多大都不知道=-=

所以我们只好换一种思路，设f[i][j]表示编号为i的节点所代表的子树在开通j个用户时的最大利润（即用户缴费-传输花费）。那么转移方程就是 f[i][j] = max{f[v][k]+f[i][j-k]-e[i].val} （特殊地，当j为0时函数值为0；叶子节点x的f[x][1]=w[x]） （v表示i的子节点，val为开通一条边的花费，w[i]为i用户缴费数额） 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define RI register int
using namespace std;
const int INF = 0x7ffffff ;
const int N = 3000 + 10 ;

inline int read() {
    int k = 0 , f = 1 ; char c = getchar() ;
    for( ; !isdigit(c) ; c = getchar())
      if(c == '-') f = -1 ;
    for( ; isdigit(c) ; c = getchar())
      k = k*10 + c-'0' ;
    return k*f ;
}
struct Edge {
    int to, next, val ;
}e[N<<1] ;
int n, m ; int head[N], f[N][N], w[N] ;  // f记录最大利润 
inline void add_edge(int x,int y,int z) {
    static int cnt = 0 ;
    e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt, e[cnt].val = z ;
}

int dfs(int x,int fa) {
    f[x][0] = 0 ;
    if(x > n-m) {
        f[x][1] = w[x] ; return 1 ;
    }
    int tot = 0 ; 
    for(int i=head[x];i;i=e[i].next) {
        int y = e[i].to ; if(y == fa) continue ;
        tot += dfs(y,x) ;
        for(int j=tot;j;j--) {
            for(int k=0;k<=j;k++) {
                f[x][j] = max(f[x][j],f[y][k]+f[x][j-k]-e[i].val) ;
            }
        }
    }
    return tot ;
}

int main() {
    n = read(), m = read() ;
    int mm = n-m ;
    for(int i=1;i<=mm;i++) {
        int k = read() ;
        for(int j=1;j<=k;j++) {
            int x = read(), z = read() ;
            add_edge(i,x,z) ; add_edge(x,i,z) ;
        }
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j] = -INF ;
    for(int i=n-m+1;i<=n;i++) w[i] = read() ;   
    dfs(1,0) ;
    for(int i=m;i>=0;i--) {
        if(f[1][i] >= 0) {
            printf("%d",i) ; return 0 ;
        }
    }
}