对于样例,为何不能直接连接 A->F ?
查看原帖
对于样例,为何不能直接连接 A->F ?
461275
jiao513楼主2022/12/25 23:03

题目中对于直径的定义:

一个牧场的 直径 就是牧场中 最远 的两个牧区的距离(本题中所提到的所有距离指的都是 最短的距离)。

且题目允许两条路径在中途相交:

注意,如果两条路径中途相交,我们不认为它们是连通的。只有两条路径在同一个牧区相交,我们才认为它们是连通的。

在样例中有两个牧场的情况:

{A,B,C,D,E} 与 {F,G,H}

题目中并没有要求,找出的路径应当尽可能小。显然,我们可以用第一个牧场中的任意一个牧区第二个牧场中的任意一个牧区连接,都可使得两个牧区成为一个牧区。
说明/提示中:

最优解是连接 C 牧区和 G 牧区,连接后图上只有一个牧场。这个牧场的直径为 A→B→C→G→F,长度约为 22.071068。可以证明不存在更优的方案。

为何舍近求远,而不是直接连接 A F ?

2022/12/25 23:03
加载中...