给定一个无向图其中有两个连通块要求在两个连通块之间添加一条边使得原图中第一个顶点和最后一个顶点之间的最短路径最长。
要使原图中第一个顶点和最后一个顶点之间的最短路径最长,可以在两个连通块之间添加一条权重最大的边。
假设原图中的两个连通块分别为连通块A和连通块B,其中连通块A包含第一个顶点,连通块B包含最后一个顶点。
为了使最短路径最长,我们可以考虑在连通块A中选择一个顶点a,连通块B中选择一个顶点b,然后在a和b之间添加一条边。这条边的权重应该尽量大,使得原图中的最短路径变得最长。
具体的做法是,遍历连通块A中的所有顶点a,遍历连通块B中的所有顶点b,计算顶点a和顶点b之间的距离。选择其中距离最远的一对顶点a和b,然后在a和b之间添加一条边,权重为这对顶点之间的距离。
这样,通过在两个连通块之间添加一条权重最大的边,就可以使原图中第一个顶点和最后一个顶点之间的最短路径最长。
原文地址: https://www.cveoy.top/t/topic/hSVz 著作权归作者所有。请勿转载和采集!