题解 P1273 【有线电视网】

我们令 $f(i,j)$ 表示以 $i$ 为根节点的子树中,选择 $j$ 个客户后剩余的金钱。

那么转移方程为

$f(i,j)=max(f(i,j),f(i)(j-k)+f(p)(k))$

其中 $p$ 表示 $i$ 的所有儿子。我们一个个的枚举它们。

代码如下。

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
using namespace std;

struct edge
{
    int v;
    int w;
     edge operator = (const edge &x)
     {
         v = x.v;
         w = x.w;
         return *this;
     }
};

const int MAXN = 5000;
int n, m;
int w[MAXN], s[MAXN], f[MAXN][MAXN];
vector<edge> e[MAXN];

void dfs(int p, int fa)
{
    f[p][0] = 0;
    for (auto i : e[p])
    {
        int v = i.v;
        if (v != fa)
        {
            dfs(v, p);
            for (int j = s[p]; j > -1; --j)
            {
                for (int k = s[v]; k > -1; --k)
                    f[p][j + k] = max(f[p][j + k], f[p][j] + f[v][k] - i.w);
            }
            s[p] += s[v];
        }
    }
    if (e[p].size() == 1)
    {
        f[p][1] = w[p];
        s[p] = 1;
    }
    return; 
} 

int read()
{
    int x;
    scanf("%d", &x);
    return x;
}

int main()
{
    n = read();
    m = read();
    for (int i = 0; i < 3000; ++i)
    {
        for (int j = 0; j < 3000; ++j)
            f[i][j] = -1e9;
    }
    for (int i = 1; i < n - m + 1; ++i)
    {
        int k = read();
        for (int j = 0; j < k; ++j)
        {
            int A = read(), C = read();
            e[i].push_back((edge){A, C});
            e[A].push_back((edge){i, C});
        }
    }
    for (int i = n - m + 1; i < n + 1; ++i)
        w[i] = read();
    dfs(1, -1);
    for (int i = m; i > -1; --i)
    {
        if (f[1][i] >= 0)
        {
            printf("%d\n", i);
            return 0;
        }
    }
    return 0;
}

发表于 2017-09-18 19:46:52 in 题解