我要招人

去企业版

首页 > 试题广场 >

Rinne Loves Edges

[编程题]Rinne Loves Edges

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。

她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 $w_i$

现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度为 1 的点都不能到达 S。

定义删除一条边的代价为这条边的边权，现在 Rinne 想知道完成这个游戏的最小的代价，这样她就能轻松到达 rk1 了！作为回报，她会让你的排名上升一定的数量。

输入描述:

第一行三个整数 N,M,S，意义如「题目描述」所述。

接下来 M 行，每行三个整数 u,v,w 代表点 u 到点 v 之间有一条长度为 w 的无向边。

输出描述:

一个整数表示答案。

示例1

输入

输出

说明

需要使得点 2,3,4 不能到达点 1，显然只能删除所有的边，答案为 3

示例2

输入

输出

说明

需要使得点 4 不能到达点 1，显然删除边 是最优的。

备注:

，保证答案在 C++ long long 范围内。

算法知识视频讲解

_LRJ_

发表于 2020-04-07 15:56:54

首先我们可以注意到最后一行m=n-1,那么这个无向连通图就是一棵树了。那么再仔细的分析下，题目要求除了s之外度为1的点都不能到达s，那么除了s之外的度为1 的点就是叶子节点了，那么问题转化为了如何删掉边权最短的一些边，从而使得s到不了任何一个（注意是任何一个）叶子节点。思索了一下，这个题应该可以展开全文

pandaC222

发表于 2026-03-07 10:53:58

最开始读题，很容易想到用dfs，但是又得保证全局最优解，这时候只用dfs就不行了，需要用dfs加dp，所以这是一道树形dp我们只需要推出状态转移方程除了s以外度为1的点，不难想到就是叶节点，我们遍历到叶节点时将叶节点的dp值初始化为INF，因为我们最开始肯定想把连着叶节点的那条边删去，后面再做优化，展开全文

AliLexiWalker

发表于 2026-03-07 14:04:25

这题看起来是一般图，实际上数据写死了 M=N-1，所以就是一棵树。而我们的目标是：把 S 和“原图里所有度为 1 且不是 S 的点（叶子）”隔开，删边代价最小。也就是说：在树上把 S 和这些叶子断开，最小割代价是多少。把树以 S 为根做树形DP。定义： has[u]：u 的子树里有没有“ 展开全文

Kur1su

发表于 2020-03-31 14:58:26

Solution Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long LL; const int N = 1 展开全文

shyyhs

发表于 2020-04-09 18:56:03

一个点连几条边就是度为几?所以度为1就是树最外边的那个点..还有题目并不要考虑删完后的情况.先插个图题目就是要让4 5 6 8 9这些点道不了1.让你删除一些边,使得删除的边权最小.那么怎么做呢..这个题目还是很简单的..设立dp[i]为底面的点都到不了i点的最小代价.那么dp[i]= min(vu 展开全文

19_hanhan

发表于 2020-05-05 08:34:53

题目题目描述： Rinne 最近了解了如何快速维护可支持插入边删除边的图，并且高效的回答一下奇妙的询问。她现在拿到了一个 n 个节点 m 条边的无向连通图，每条边有一个边权 wi。现在她想玩一个游戏：选取一个 “重要点” S，然后选择性删除一些边，使得原图中所有除 S 之外度展开全文

LB_tq

发表于 2020-03-31 12:15:27

Solution 由题意可知给定的图是一棵树。树上的最优化问题可以想到树形。按照常用的状态设计方式，可以设为根节点为的最少代价。使以为根的子树的叶子节点无法到达的方式有两种：割断与直接相连的边割断与的子节点直接相连的边两种方式取最小值即可。故状态转移方程为其展开全文

olone

发表于 2026-03-07 10:28:18

#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 展开全文

腌萝卜干

发表于 2026-03-07 11:15:00

子树的决策问题一般都是树形, 定义状态表示表示度数为的点无法到达的最小代价情况, 切断当前边代价为情况, 切断子树的某条边代价为两种取最小值即可 #include <bits/stdc++.h> #define x first #define y second #define 展开全文

wxyww

发表于 2020-04-02 23:05:33

solution 因为m=n，所以题目要求也就是要求断掉一些边，使得根与叶子节点不连通，用f[i]表示以i已经无法到达它子树中的所有叶子节点的最小花费。转移的时候分两种情况，如果断开当前点与父亲相连的边，那么其子树中的边可以都不断开，花费为0.如果不断开当前点与父亲相连的边，那么答案就是其儿子的f 展开全文

问题信息

思维题

难度：

1条回答 6收藏 71浏览

Rinne Loves Edges

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

相关试题