每日一题4月1日 Rinne Loves Edges 树形dp,dfs

Rinne Loves Edges

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

每日一题居然放了一个简单题。

题意:
给一个无向图,n个点n-1条边,每条边上有边权,现在给定一个根s,求以s为根的图中,删掉一些边要让所有度为1的点不能连接到s。

思路:
根据题意,给出的图就是一颗树。那么就是问删一些边让叶子节点无法连通到根s。
我们可以考虑某个点x,假设要让x子树的叶子节点无法连通s,我们要么删x-s这条边,要么删除x子树中的边。
那么我们可以dfs,我们维护f[x]为以x为根让叶子节点无法连接到x的最小删边代价。
显然,枚举x中的所有相连节点v,可以得到转移方程:
f[x]=min(w(x,v),f[v])
注意叶子节点的时候只能选删叶子节点边。
O(n)可以解决。

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int tot,head[100005],vis[100005];
struct node{
    int w,next,to;
}p[200050];
void init(){
    memset(head,-1,sizeof(head));
}
void add(int x,int y,int z){
    tot++;
    p[tot].to=y;
    p[tot].next=head[x];
    p[tot].w=z;
    head[x]=tot;
}
long long dfs(int x){
    vis[x]=1;
    long long ans=0;
    for(int i=head[x];~i;i=p[i].next){
        int y=p[i].to;
        if(vis[y])continue;
        vis[y]=1;
        int w=p[i].w;
        long long tmp=dfs(y);
        if(tmp==-1)ans+=w;
        else ans+=min(1ll*w,tmp);
    }
    if (ans==0)return -1;   //到叶子节点了。
    return ans;
}
int main()
{
    cin>>n>>m>>s;
    init();
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    cout<<dfs(s)<<endl;
    return 0;
}
全部评论

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
投递美团等公司9个岗位
点赞 评论 收藏
分享
Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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