【蓝桥杯】蓝桥杯双周赛第二场E题

这篇具有很好参考价值的文章主要介绍了【蓝桥杯】蓝桥杯双周赛第二场E题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

知识点:树的直径 

题目

        过年了。

        蓝桥村可以抽象为n个节点,n - 1条边的一棵树,每条边有边权长度wi。

        小蓝可以选择任意一个点作为起点,然后选择一条路径,可以访问每一个节点最少一次。他想知道最短的路径长度是多少。

输入格式

        第一行输入一个整数n,表示节点的数量。

        加下来n - 1行,每行三个整数vi,ui,wi,表示(vi,ui)存在一条wi的边。

输出格式

        输出一个整数,表示最短路径。

思路

        我们可以从任意一个节点开始,必须至少到达每个节点最少一次。我们很容易得到最短路程是所有道路长度之和的两倍减去这棵树的直径。数的直径可以从树中任意一点出发,找到距离这个点L(第一遍DFS),再从L出发到达树中距离S最远的点L,S到L这段距离就是树的直径。

 代码

#include<bits/stdc++.h>
#define int long long
#define N 200010 // 要建无向边,开两倍大小
using namespace std;

int n;
int e[N],ne[N],h[N],w[N],idx;// 邻接表四件套
int dist[N];// 该点到起始点的距离
bool st[N];// 判断该点是否被便利过
int ans;
void add(int a,int b,int c)
{
    w[idx] = c,e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int u)
{
    st[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j] && dist[j] > dist[u] + w[i])
        {
            dist[j] = dist[u] + w[i];
            st[j] = true;
            dfs(j);
        }
    }
}

int32_t main()
{
    memset(h,-1,sizeof(h));
    cin >> n;
    for(int i = 0; i < n - 1; i ++)// 建树,无向边
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
        ans += c * 2;
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;// 从任意一点开始
    dfs(1);
    int maxx = -1,address = -1;
    for(int i = 1; i <= n; i ++)// 找到距离这个点最远距离的点
    {
        if(dist[i] > maxx)
        {
            maxx = dist[i];
            address = i;
        }
    }
    for(bool & i : st)// 将数据重置
    {
        i = false;
    }
    memset(dist,0x3f,sizeof(dist));
    dist[address] = 0;
    dfs(address);
    maxx = -1;
    for(int i = 1; i <= n; i ++)// 找到最远的距离(树的直径)
    {
        if(dist[i] > maxx)
        {
            maxx = dist[i];
        }
    }
    cout << ans - maxx << endl;// 所有路程之和的两倍减去树的直径就是最短距离
    return 0;
}

 文章来源地址https://www.toymoban.com/news/detail-734747.html

 

到了这里,关于【蓝桥杯】蓝桥杯双周赛第二场E题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《蓝桥杯真题》:2022单片机省赛第二场_客观题(第十三 / 13届第二场)

    声明:我仅是贴出我认为正确的答案,不是标准答案! 解析:打开ISP看到下面两个文件类型,我就选了 BC 解析:比赛给的《STC15系列单片机用户手册》P301,可以看到是可以位寻址的都能够被8整除,不能够被8整除的无法进行位操作,SCON的地址为98H,P4的地址为C0H,可以位寻址

    2023年04月08日
    浏览(53)
  • 第十三届蓝桥杯嵌入式省赛第二场真题(基于HAL库的巨简代码+超级详解)

    相关说明: 开发板:CT117E-M4(STM32G431RBT6) 开发环境: CubeMX+Keil5 涉及题目:第十三届蓝桥杯嵌入式省赛第二场真题 CubeMX配置、主要函数代码及说明: 1.使能外部高速时钟: 2.配置时钟树: 3.GPIO: 4.TIM2(通道2 PA1输出脉冲信号): 5.UART: 6.NVIC优先级配置    博主参加的是第一场

    2023年04月09日
    浏览(64)
  • 1014蓝桥算法双周赛,学习算法技巧,助力蓝桥杯

    家人们,我来免费给大家送福利了!!! 【1014蓝桥算法双周赛 】 蓝桥杯全国软件和信息技术专业人才大赛是由工业和信息化部人才交流中心举办的全国性IT学科赛事。参赛高校超过1200余所,累计参赛人数超过40万人。该赛事连续两年被列入中国高等教育学会发布的“全国普

    2024年02月08日
    浏览(41)
  • 蓝桥杯 第一场算法双周赛题解(前五题)

    题目链接在此😁:第 1 场算法双周赛 - 蓝桥云课 为什么只有前5道题的题解呢?(懂的都懂~🤐) 考察:简单逻辑判断 问题描述 小蓝和小桥玩斗地主,小蓝只剩四张牌了,他想知道是否是“三带一”牌型。 所胃三带一”牌型,即四张手牌中,有三张牌一样,另外一张不与其

    2024年02月08日
    浏览(45)
  • 「蓝桥·算法双周赛」第一场公开赛【待补题填坑】

    给定四个字符,判断是否其中有三个相同,另一个与他们不同  二叉树性质问题,不了解二叉树也完全可以做。 要注意的是每次都从第一行的第一个点开始走,给一个字符串按照它走,输出最后的结果就行。 往左走坐标就变成了2*pos-1,往右就变成了2*pos 画个树理解一下就好

    2024年02月07日
    浏览(50)
  • 蓝桥杯1024第 2 场算法双周赛题解+Ac代码

    提醒:篇幅可能有点长,为了方便,大家可以直接看目录快速查找想要的内容 1.新生【算法赛】 - 蓝桥云课 (lanqiao.cn) input: output: 1.对于每一块地板,如果能被凑出来,那么一定是2*3地砖组合出来的,无论2*3地砖怎么放都为6的倍数,故长为n,宽为m的地板,n*m%6==0一定成立 2.这里

    2024年02月06日
    浏览(43)
  • 第十四届蓝桥杯单片机第二场模拟赛程序

    第十四届蓝桥杯单片机第二场模拟赛程序(少量bug) 题目来源于4T评测网 www.4t.wiki 使用大赛组委会提供的国信长天单片机竞赛实训平台,完成本试题的程序设计与调试。程序编写、调试完成后,选手需通过考试系统提交以准考证号命名的hex文件。不符合以上文件提交要求的作

    2023年04月14日
    浏览(56)
  • 2022 第十三届蓝桥杯大赛软件赛省赛(第二场),C/C++ 大学B组题解

    2022 第十三届蓝桥杯大赛软件赛省赛(第二场),C/C++ 大学B组题解 补题链接:地址 第1题 —— 练习 (5分) 题意:过了样例交上去0分,问可能是ABC的哪一种 显然都是,答案:ABC 第2题 —— 三角回文数 (5分) 题意:求第一个大于某2e8的数的回文数,且满足他可以等于1+2+…

    2023年04月09日
    浏览(56)
  • CSDN周赛第48期

    不知不觉又过去两期周赛,相应地,题解也落下了。而当我再回去想下载考试报告时。。。 现在更新的速度有这么快了么? 可惜题目还是考过的旧题,尤其对我们这种老油子来说,最大的好处是省去了阅读理解的烦恼。 平心而论,本期四道题,对初学者来说,还是有一定难

    2024年02月01日
    浏览(42)
  • [LeetCode周赛复盘] 第 111 场双周赛20230819

    T1 对向双指针。 T2 子序列/同向双指针。 T3 LIS/状态DP。 T4 数位DP。 2824. 统计和小于目标的下标对数目 1. 题目描述 2. 思路分析 类似两数之和,由于顺序无关,把数据排序。 设置l,r=0,n-1。 若a[l]+a[r]target,则a[l]+ 任意a[l+1…r]都target。则这r-l个数都可以和l组队。 3. 代码实现 2825

    2024年02月11日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包