0%

【每日一题】Rinne Loves Edges题解

题目链接

Solution

这题目很坑,把重要的信息放在了最后面,即$M=N-1$,而且还是一个无向连通图。。除了输入N还要输入M不知道意义何在

题目转换一下即要使原来的除了S以外的叶子节点全部都不能和S连通。

显然我们需要以$S$点作为根节点,然后才好做。

令$dp[u]$代表令节点$u$的子树的叶子节点均到达不了节点$u$。那么就有

$$
dp[u]=\begin{cases}
inf,&u\text{是叶子节点}\
\sum\limits_{v,w\in \text{u的子节点}}{min(dp[v],w)},&u\text{不是叶子节点}
\end{cases}
$$

当$u$是叶子节点的时候,他无法完成这样的操作,所以$dp[u]$为$\infty$。

当$u$不是叶子节点的时候,对于它的儿子而言,要么删掉到它的儿子的这一条边,要么使用它的儿子就可以做到的最好的情况。这两种情况做一个比较选择最优的方案即可。

时间复杂度$O(n)$ 空间复杂度$O(n)$

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
// 链式前向星
struct edge {
int v; ll w; int nxt;
} G[N << 1]; // 双向边 要开两倍
int h[N], tot;
// 增加双向边
void addedge(int u, int v, ll w) {
G[tot] = {v, w, h[u]}; h[u] = tot++;
G[tot] = {u, w, h[v]}; h[v] = tot++;
}
ll dp[N];
void dfs(int u, int f) {
bool isLeaf = true;
for(int i = h[u]; ~i; i = G[i].nxt) {
const int v = G[i].v;
if(v != f) {
isLeaf = false;
dfs(v, u);
dp[u] += min(dp[v], G[i].w); // 选择最优解
}
}
// 如果是叶子 赋值为inf 迫使dp[fa[u]]只能选择这条边
if(isLeaf) dp[u] = LLONG_MAX;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(h, 0xff, sizeof h); tot = 0; // 初始化
int n, m, s; cin >> n >> m >> s;
for(int i = 0; i < m; i++) {
int u, v; ll w; cin >> u >> v >> w;
addedge(u, v, w);
}
dfs(s, -1);
cout << dp[s] << '\n';
}

回到开头