首页 > 小A与欧拉路
头像 __故人__
发表于 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)次(即在这条边连接的两个点之间再加一条边权相同的边),求所有可能新形成的图中欧拉路的最短长度。欧拉路:从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边只通过恰好一次。 做法: 不难发现每条树边顶多用次, 展开全文

等你来战

查看全部