有一个有N个节点和N-1个连接链路的计算机网络。每个连接链接都有一个与之关联的时间。
我们得到了一个初始网络设置,如图所示。计算机通过双向链路连接。
网络时间定义为任何一对节点(计算机)之间的最大时间。
在给定的图中,网络时间为 25(节点 5、2、3、6)。
我们的任务是通过删除确切的一条边并在任何其他地方添加这条边来最大化这个网络时间。条件是:
1. 边缘的一端或两端都可以移除和添加。
2. 经此操作后的网络将是一棵生成树,每对顶点之间仅存在一条路径。
上述网络可以转换为下图,以实现最大网络时间为 25。 约束条件是:N,计算机(节点)的数量在 4 到 2000 之间。理想:执行时间在 1 秒内的最佳解决方案(C 和 C++)。