题解 P1273 【有线电视网】
scallop
2017-09-18 19:46:52
我们令 $f(i,j)$ 表示以 $i$ 为根节点的子树中，选择 $j$ 个客户后剩余的金钱。
那么转移方程为
$f(i,j)=max(f(i,j),f(i)(j-k)+f(p)(k))$
其中 $p$ 表示 $i$ 的所有儿子。我们一个个的枚举它们。
代码如下。
```cpp
#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;
}
```