Luogu1268树的重量

题中给出了邻接矩阵&＃xff0c;而且 n 比较小&＃xff0c;可以先考虑 Floyd 那样的做法

一些三个点组成的点集他们之间的关系是满足 dst[i][j] &＃61; dst[i][k] &＃43; dst[k][j]
这些点的位置关系是可以先确定下来的

但是有些点之间的距离连出来会不一样&＃xff0c;甚至还有些点加不到图中

考虑加入了图中但是距离不对的点&＃xff0c;他们中间一定至少有个中转点
而在其他点的距离都计算正确的情况下&＃xff0c;
枚举所有点作为中转点后取最小值
最小值一定是距离不正确的点对中的一个点&＃xff08;设为 k&＃xff09;向上连接的边长
用这个式子计算&＃xff1a;val &＃61; (dst[i][j] &＃43; dst[j][k] &＃43; dst[k][i]) / 2 - dst[i][j]

简(hu)单(luan)证明一下就是如果最小值不是我们想要的东西的话
那一定是一个较大的值&＃xff0c;而存在较小值一定是较大值是较大值多走了一条/些边
&＃xff08;自己画一条链计算端点的值随便找几个点试一下就发现了&＃xff09;

 感觉菊花图没法做&＃xff0c;像是这样&＃xff1a;

其实这种时候随意找两个点&＃xff0c;他们之间的距离是正确的
再按照上面的计算方式是可以计算的

具体在实现的时候&＃xff0c;发现他可以像 Floyd 差不多写

只要把他之前加入的都算上求最小值就行&＃xff0c;
顺序讲道理是无所谓的只要把他和其他的都计算一遍就好

为了方便就从 1 到 n 依次加入了

 代码&＃xff1a;