网站建设工作会议,wordpress主题结构,东莞产品展厅设计公司,wordpress检测替换Rinne Loves Edges 时间限制#xff1a;1秒 空间限制#xff1a;128M 知识点#xff1a;思维题 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff0c;…Rinne Loves Edges时间限制1秒 空间限制128M知识点思维题网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述R i n n e RinneRinne最近了解了如何快速维护可支持插入边删除边的图并且高效的回答一下奇妙的询问。她现在拿到了一个n nn个节点m mm条边的无向连通图每条边有一个边权w i w_iwi​现在她想玩一个游戏选取一个 “重要点”S SS然后选择性删除一些边使得原图中所有除S SS之外度为1 11的点都不能到达S SS。定义删除一条边的代价为这条边的边权现在R i n n e RinneRinne想知道完成这个游戏的最小的代价这样她就能轻松到达r k 1 rk1rk1了作为回报她会让你的排名上升一定的数量。输入描述第一行三个整数N , M , S N,M,SN,M,S意义如「题目描述」所述。接下来M MM行每行三个整数u , v , w u,v,wu,v,w代表点u uu到点v vv之间有一条长度为w ww的无向边。输出描述一个整数表示答案。示例1输入4 3 1 1 2 1 1 3 1 1 4 1输出3说明需要使得点2 , 3 , 4 2,3,42,3,4不能到达点1 11显然只能删除所有的边答案为3 33示例2输入4 3 1 1 2 3 2 3 1 3 4 2输出1说明需要使得点4 44不能到达点1 11显然删除边2 ↔ 3 2↔32↔3是最优的。备注2 ≤ S ≤ N ≤ 10 5 , M N − 1 2≤S≤N≤10^5,MN−12≤S≤N≤105,MN−1保证答案在C l o n g l o n g C \ long \ longClonglong范围内。解题思路本题核心是通过树形DPDFS求解最小删除代价因题目中M N − 1 MN-1MN−1且图连通本质为以S SS为根的树首先明确目标是切断所有叶子节点度为1 11且非S SS到S SS的路径最小化删除边的代价定义d p [ x ] dp[x]dp[x]为切断以x xx为根的子树中所有叶子节点到x xx路径的最小代价。D F S DFSDFS遍历树时若x xx是叶子节点非S SS则d p [ x ] dp[x]dp[x]设为无穷大必须删除连接它的边否则对每个子节点v vvd p [ x ] dp[x]dp[x]累加m i n ( d p [ v ] , w ) min(dp[v], w)min(dp[v],w)选择切断子树内部路径或直接删除x − v x-vx−v边的较小代价。最终d p [ S ] dp[S]dp[S]即为切断所有叶子到S SS路径的最小代价。该方法时间复杂度O ( N ) O(N)O(N)适配N ≤ 1 e 5 N≤1e5N≤1e5的规模通过树形D P DPDP精准计算最优删除策略的代价。总结核心逻辑将问题转化为树形D P DPDP每个节点选择切断子树内部或删除当前边的最小代价。关键操作D F S DFSDFS遍历树叶子节点设为无穷大非叶子节点累加子节点的最小代价。结果输出根节点S SS的d p dpdp值即为切断所有叶子路径的最小删除代价。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll p1e47;constll INF1e18;vectorplld[N];ll dp[N],vis[N];voiddfs(ll x){vis[x]1;ll op1;dp[x]0;for(autoe:d[x]){ll ve.first;ll we.second;if(!vis[v]){op0;dfs(v);dp[x]min(dp[v],w);}}if(op)dp[x]INF;}intmain(){ll n,m,s;cinnms;while(m--){ll u,v,w;cinuvw;d[u].emplace_back(v,w);d[v].emplace_back(u,w);}dfs(s);coutdp[s]endl;return0;}