牛客每日一题：Rinne Loves Edges

Rinne Loves Edges

题意

这道题还是比较有意思的。题目的意思简要概括一下大概是：我们有 n 个结点的一棵树，给出一个重要结点 S ，再给出边的信息，每一条边都有相应的边权，我们可以删除任意边。要求我们求出让原图中所有除 S 之外度为 1 的点都不能到达 S 的删除边权和的最小值。

思路

首先，这道题给出的是一颗树，我们可以利用这一性质来处理这道题。我们可以以 S 为根节点建树，那么我们的目标就转化成：删除任意边，使所有叶子节点都不能到达根节点。

基于这一想法，我们可以使用确定：使用深搜+回溯来解决这道题。

我们可以想到对于一个有多分支的结点而言，想要让该子树中的所有叶子结点都不能到达根节点，要么断开子树中的边，要么断开自己到根节点路径上的边。好，那么我们可以确定搜索的方向了：从根节点向下搜索，回溯带来子树中断开的最小值，再与当前节点连接子树的边的值相比较，取较小者向上回溯。

这个思路的时间复杂度十分优秀，为 O(n) ，能够完美地解决这道题。

正解代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

int n,m,s;
int fa[N];

vector< pair<int,int> >e[N];

inline int dfs(int x,int fa)
{
int ans = 0;
bool flag = false;
for(auto i:e[x])
{
if(i.first == fa) continue;
flag = true;
ans += min(dfs(i.first, x), i.second);
}
if(!flag) return 0x3f3f3f3f;
return ans;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
cout<<dfs(s,0);
return 0;
}

以上就是这篇文章的全部内容了。