【每日一题】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

#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';
}