首页
比赛
题库
课程
竞赛讨论区
登录
/
注册
去牛客
首页
>
小A与欧拉路
13条解析
开通博客写题解
__故人__
发表于 2020-11-03 17:53:27
分析 我们对于不定根的树形结构的题目,我们首先应该考虑定根考虑。考虑从节点 出发。那么我们得到的最短的欧拉路一定是 ,考虑到每次走完一个子树都必须回到自身,除了最后一次。所以我们在定根之后,就是要选取 。那么我们只要取所有节点作为根的最大值。结合定义可以发现我们就是要求,树上的一条最长路径
展开全文
Kur1su
发表于 2020-11-04 11:58:32
Description 小A给你了一棵树,对于这棵树上的每一条边,你都可以将它复制任意(可以为0)次(即在这条边连接的两个点之间再加一条边权相同的边),求所有可能新形成的图中欧拉路的最短长度欧拉路:从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边只通过恰好一次 Solution 考虑欧
展开全文
Dear㉿You
发表于 2020-11-04 21:37:14
小A与欧拉路 分析 欧拉路: 该路径经过图的每一条边且仅经过一次。如果路径起点和终点相同,则称“欧拉回路”。具有欧拉回路的图称“欧拉图”。 即因为要求最短,那么path(x,y)最长即可。就是一个树的直径的模板 代码 /*树的直径*/ #include<bits/stdc++.h>
展开全文
sunrise__sunrise
发表于 2020-11-04 16:05:00
题目描述 给你n个节点的m条无向边构成个一个无向图。你可以随便选取起点,在遍历全部节点的前提下请问最少的花费是多少? Solution 首先观看样例以及解释很容易找到一条最短的路径。那么跟着这个思路,自己再手写另外一种情况。你会发现总有路径需要回退,除非全部节点是一根线,那么居然要回退是不是要选择尽
展开全文
DeNeRATe
发表于 2020-11-04 20:17:15
前置 首先我们需要知道什么是欧拉路和欧拉回路?欧拉路:指从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边通过的且只通过一次判定条件:图中只存在两个度数为奇数的点,其余全为偶数欧拉回路:欧拉回路是指起点和终点相同的欧拉路判定条件:图中所有的点度数为偶数 分析 有了前置芝士,这道题看起来就
展开全文
子希
发表于 2020-11-05 21:30:44
思路:直接想怎么去加边可能比较难想。但是虽然欧拉路不太好求,我们可以从欧拉回路着手,因为这是一棵树,如果要找到一条路,必定是每条边都经过两次(因为是一棵树,不存在任何回路,所以回路必须原路返回,即再经过原来的边一次),那么欧拉回路的权是 。欧拉回路必然满足欧拉路,接下来怎么从欧拉回路找一条最小权的欧
展开全文
林思艺
发表于 2020-11-03 19:14:32
思路 考虑最简单的情况,的情况。每条边就一定是经过两次——去和回。那么遍历完,每条边就需要复制一次,所以。由于不是回路所以可以减去从起点到终点的路径。所以我们要使起点到终点的路径最长。所以问题就是找到树的直径。答案就是。 代码 #include<bits/stdc++.h> #defin
展开全文
issue是云哥的小迷×呀
发表于 2020-11-07 08:55:35
在纸上画一棵树,发现如果是回路,每条边走两次就够了 那么不是回路,有些边就不需要走两次了 发现,任意选择两点,从端点出发,路上一旦出现分支就出去走两遍回来 这样走到两一个端点的时候,两点间的距离其实只被走了一次 这样的话就求树的直径就好了 有点像规律题呢 #include <bits/stdc
展开全文
熠丶
发表于 2020-11-05 10:44:05
前置芝士: 欧拉路:从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边只通过恰好一次 思路: 因为求欧拉路的最短长度,且可以把任意边复制任意多次(其实就是每一条边可以走多次) 由贪心的思想就是尽可能重复走短边,长边只走一次 可以任意造几个数据可得重复走的边最多走两次 所以可以得出每
展开全文
rk_no
发表于 2020-11-03 19:24:13
题目: 小A给你了一棵树,对于这棵树上的每一条边,你都可以将它复制任意(可以为0)次(即在这条边连接的两个点之间再加一条边权相同的边),求所有可能新形成的图中欧拉路的最短长度。欧拉路:从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边只通过恰好一次。 做法: 不难发现每条树边顶多用次,
展开全文
查看本题
查看本题讨论
等你来战
查看全部
“崖山数据库杯”深圳大学程序设计竞赛(热身赛)
报名截止时间:2024-03-29 22:00
牛客练习赛123
报名截止时间:2024-03-29 21:30
信息工程大学第五届超越杯程序设计竞赛(同步赛)
报名截止时间:2024-03-30 10:00
“崖山数据库杯”深圳大学程序设计竞赛(正式赛)
报名截止时间:2024-03-30 15:00
牛客2024年愚人节比赛
报名截止时间:2024-04-01 21:00
牛客小白月赛90
报名截止时间:2024-04-05 21:00
浙江理工大学 2024 年程序设计竞赛(同步赛)
报名截止时间:2024-04-06 17:00
牛客周赛 Round 39
报名截止时间:2024-04-07 21:00
牛客挑战赛74
报名截止时间:2024-04-12 22:00
华中农业大学第十三届程序设计竞赛(同步赛)
报名截止时间:2024-04-14 15:00
牛客小白月赛91
报名截止时间:2024-04-19 21:00
牛客练习赛124
报名截止时间:2024-04-26 21:30
扫描二维码,关注牛客
意见反馈
下载牛客APP,随时随地刷题