首页 > 反复横跳

摸鱼学大师

发表于 2021-09-14 20:35:17

题目的主要信息：一张带权无向图，图中任意两点间有且仅有一条路径，这是一棵无向树计算从任意点出发并访问完所有节点经过边的权值之和的最小值分析：首先，如果我们要从一个点到达其他所有点，每条边我们必须经过一次，因为任意两点之间有且仅有一条路径。然后，因为可以到树叶以后再回溯访问，再到另外的枝，展开全文

呆喵挠琴

发表于 2021-10-22 17:22:05

题目的主要信息：已知带权无向图，每个节点之间仅有一条路径求经过所有节点最小权重之和方法一：DFS 如果不考虑路径长度，那么把所有路径走一遍必定可以经过所有节点。要经过每一个节点，且每个节点之间只有一条路径，那么至少需要把所有的路径走一遍，假设权重之和为weight。在最坏的情况，每条路展开全文

Bug-Maker

发表于 2021-07-13 00:29:03

所有边的两倍减去无重复最长路径就是答案。因为题目说了任意两点之间只有一条路径，所以在我们沿着最长边走的时候，所有的分支都需要走两遍，而最长路径只需要走一遍。 class Solution {public: /** * 最短距离 * @param n int整型 * @p 展开全文

George_Plover

发表于 2021-09-13 11:28:39

题意整理：基本题意给出一棵具有个结点的无根树，给出每条边的边权，表示两个结点之间的距离。可以任意选择一个结点作为起点，按照一定的顺序访问每个结点至少一次，问经过的路径的总长度最少是多少。输出这个答案。数据范围与性质。展开全文

xqxls

发表于 2021-09-08 17:04:38

题意整理给定一张带权无向图，图中任意两点间有且仅有一条路径。求从任意点出发，访问完所有节点后，所经过边的权值和的最小值。方法一（dfs） 1.解题思路要想边权值最小，所走的路径中必定包含了最长（边权值最大）无重复节点的路径，只要求出这个路径权值和，用所有路径权值和的两倍减去最大路径权值和展开全文

查看本题

查看本题讨论

等你来战

查看全部