[POJ - 1155] TELE

发表于 | 更新于 | 分类于 ， ，
本文字数： 15k

链接

\(\text{POJ - 1155 TELE}\)

题意

  这里有\(m\)个用户想要使用电视，然而它们需要电视网络信号进行传播信号，整个电视网络由信号发射器和用户组成，它的形状是一棵树，用户是叶子结点，现在给出了连接发射器与发射器或用户之间的信号所需要花费的金钱，\(m\)个用户每个用户使用电视都会支付一些金钱，问可以观看电视的用户的数量最大是多少，以致电视网络的搭建不会亏损金钱；整颗树共\(n\)个节点，

  输入格式：第一行两个整数\(n,m\)，表示树中结点个数和叶子结点个数，树根一定是1，其他发射器编号从2到\(n-m\)，用户即叶子结点编号从\(n-m+1\)到\(n\)，接下来\(n-m\)行，第\(i\)行K A1 C1...AK CK，表示与\(i\)个发射器相连接的结点有\(k\)个，对应编号是\(a_j\)，连接\(i\)与\(a_j\)需要花费的费用是\(c_j\)，最后一行\(m\)个整数，表示\(m\)个用户使用电视会支付的金钱。

  数据范围：\(2\leq n\leq 3000,1\leq m\leq n-1\).

  输出格式：输出一行，表示电视网络搭建不亏损情况下，最多可以使用电视的用户的数量。

分析

  对于某一棵子树，假设我们考虑他的亏损情况，如果它是亏损的我们就切掉它，那么这种想法显然是不正确的，如果他有兄弟结点，并且兄弟结点不亏损，那么它们的父亲的那颗子树，显然是未知的；

  我们换一种思路，考虑求出当前子树的最大收入，\(f[i][j]\)表示在以\(i\)为根节点的子树中选取\(j\)个用户即\(j\)个叶子节点的最大收入，之后我们求出了节点1的所有状态，那么我们它的状态，从\(m\)到1，找到第一个满足\(f[1][j]\)的\(j\)即可，输出它。

  关于中间的细节，如果搜索到了叶子结点\(x\)我们就记录\(f[x][1]=c[x]\)，同时使用\(sz[i]\)记录以\(i\)为根的子树中包含的用户数量，在以\(i\)为根的子树中进行背包，\(sz[i]\)即为背包容量，在叶子结点\(x\)显然有\(sz[x]=1\)，对于\(f\)初始化成\(-\infty\)，每当我们搜索进入一个新节点\(x\)我们就初始化\(f[x][0]=0\)，回溯的时候进行背包即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 3005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

int n, m, k, a[MAXN][MAXN], c[MAXN], f[MAXN][MAXN], sz[MAXN];
vector<int> vec[MAXN];

void dfs(int u, int fa) {
    f[u][0] = 0;
    if (c[u]) {
        sz[u] = 1;
        f[u][1] = c[u];
        //cout << c[u] << endl;
        return;
    }
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if (v == fa) continue; 
        dfs(v, u);
        sz[u] += sz[v];
        for (int j = sz[u]; j > 0; j--)
            for (int k = 1; k <= j; k++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - a[u][v]);
    }
}

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    memset(f, -INF, sizeof(f));
    cin >> n >> m;
    for (int i = 1; i <= n - m; i++) {
        cin >> k;
        int v, w;
        for (int j = 1; j <= k; j++) {
            cin >> v >> w;
            vec[i].push_back(v);
            vec[v].push_back(i);
            a[i][v] = a[v][i] = w;
        }
    }
    for (int i = n - m + 1; i <= n; i++)
        cin >> c[i];
    dfs(1, 0);
    for (int i = n; i > 0; i--) {
        if (f[1][i] >= 0) {
            cout << i;
            return 0;
        }
    }
}