AC代码

https://codeforces.com/contest/1764/submission/184176192

题意：

Doremy有一个具有n个顶点的边加权树，其权重为1到10^9之间的整数。

她对其进行了n(n+1)/2次实验。

在每个实验中，Doremy选择顶点i和j，使得j≤i,然后连接顶点i和j，其边权重为1. 

在图中正好有一个循环（或当i=j时的自循环）。

Doremy将f(i，j)定义为从每个顶点到循环的最短路径的长度之和。

形式上，设dis_(i，j)(x，y)是添加权重为1的边（i，j）时顶点x和y之间的最短路径的长度，

S_(i，j)是添加边（i、j）时在循环上的顶点集。然后

f(i，j)=∑x=1...n（min y∈S_(i，j)  dis_(i，j)(x，y)）。

Doremy记下f（i，j）的所有值，满足1≤j≤i≤n. 给定f(i，j)的数值，你能帮她恢复树吗？

保证至少存在一棵合适的树。

题解：

图论

1. 求d[i][j], 1≤j≤i≤n,  即任意两个顶点之间的距离。

2. 在d[i][j], 1≤j≤i≤n, 基础上求一棵最小生成树。