【每日一题】Rinne Loves Edges

Rinne Loves Edges

https://ac.nowcoder.com/acm/problem/22598

思路
注意题中的M M=N-1 并且图联通 说明这是一棵树
然后题意就是说 让重要点s 到不了其他度为1的点
度为1的点 那不就是叶子节点嘛
所以我们只要从点s开始dfs,计算出到叶子节点的路上的最短的边权加起来即可
复杂度O(n)
用dp[x]表示节点x到每个叶子节点的最小边权值
那么dp[x]+=min(dp[u],v) 其中x是当前节点,u是x的子节点,v表示u-x的边权

想好之后 就可以快乐ac了

注意对根节点赋值一个无穷大的数 还有记得开ll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    int to;
    ll v;
};
ll dp[100005];
vector<node> e[100005];
bool vis[100005];
int n,m,s;
void dfs(int x){

    int f=0;
    for(int i=0;i<e[x].size();i++){
        if(!vis[e[x][i].to]){
            f=1;
            vis[e[x][i].to]=1;
            dfs(e[x][i].to);
            dp[x]+=min(e[x][i].v,dp[e[x][i].to]);
        }
    }
    if(!f) dp[x]=1e18;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>s;
    for(int i=1,x,y;i<n;i++){
        ll d;cin>>x>>y>>d;
        e[x].push_back({y,d});
        e[y].push_back({x,d});
    }
    vis[s]=1;
    dfs(s);
    cout<<dp[s]<<endl;

    return 0;
}
每日一题 文章被收录于专栏

每日一题专栏

全部评论

相关推荐

xdm怎么说&nbsp;要被拷打了&nbsp;担心是KPI
丹田:面就完了,就当日薪四位数的大佬免费给给你面试。
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
05-09 13:22
门头沟学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务