传送门：https://www.luogu.com.cn/problem/P2458
题意
给一棵树，在树上安置保安，一条边的两个端点至少安置一个保安，保安都有费用。 问符合情况的最小费用是多少。
思路
因为一条边的两个端点必须要有一个，可以有两个，所以这是不限制父亲和儿子关系的。
如果一条边的两个端点都选，那一定不会是最小费用，所以只需要选一点即可。
对于一个点选不选，对父亲和儿子选不选都有影响，所以设f[u][0/1/2]。 f[u][]表示以u为根的子树。
- f[u][0]表示u自己选
- f[u][1]表示自己不选，儿子选
- f[u][2]表示自己不选，父亲选
转移方程：
自己选，不妨碍其他点的选择，即
- $f[u][0]+=\sum_{v\in g[u]}min(f[v][0],f[v][1],f[v][2])$
父亲选，所以自己不用选了，只需要加上儿子的最小费用，即
- $f[u][2]+=\sum_{v\in g[u]} min(f[v][0]+f[v][1])$
儿子选，对于所有儿子，肯定不会全部都选，选择最小的儿子即可，即
- $f[u][1]+=\sum_{v\in g[u]除最小}f[v][1]+f[v_{最优}][0]$
对于f[u][1]，我们怎么找到最小的呢？
记录$mn=min(mn,f[v][0]-f[v][1])$
1
2
3
4
5
6
7
8
9
10
11
| bool flag = 1;
if(f[v][0] <= f[v][1]) {
flag = 0;
f[u][1] += f[v][0];
}
else {
f[u][1] += f[v][1];
mn = min(mn, f[v][0] - f[v][1]);
}
}
if(flag) f[u][1] += mn;
|
Code
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
| ##include "bits/stdc++.h"
using namespace std;
const int N = 1e4 + 10;
vector<int> g[N];
int val[N];
int f[N][3];
void dfs(int u, int fa) {
f[u][0] = val[u];
bool flag = 1;
int mn = 1e9;
for(auto v : g[u]) {
if(v == fa) continue;
dfs(v, u);
f[u][0] += min(f[v][0], min(f[v][1], f[v][2]));
f[u][2] += min(f[v][0], f[v][1]);
if(f[v][0] <= f[v][1]) {
flag = 0;
f[u][1] += f[v][0];
}
else {
f[u][1] += f[v][1];
mn = min(mn, f[v][0] - f[v][1]);
}
}
if(flag) f[u][1] += mn;
}
void solve() {
int n; cin >> n;
for(int i = 1;i <= n; i++) {
int id, m; cin >> id >> val[id] >> m;
for(int j = 1;j <= m; j++) {
int v; cin >> v;
g[v].eb(id);
g[id].eb(v);
}
}
dfs(1, -1);
cout << min(f[1][0], f[1][1]) << endl;
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/25/p2458-sdoi2006/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！