由网友(留不回去的是眼泪﹌)分享简介：假设我们有一个加权图G和it.we的生成树吨要更改边权重，因此T为一个最小生成树和所有的总和| w_i - w'_i |是最小的，其中w_i是边缘i_th的重量和w'_i是边缘i_th的权重改变后。suppose we are given a weighted graph G and a spanning tre...

假设我们有一个加权图G和it.we的生成树吨要更改边权重，因此T为一个最小生成树和所有的总和| w_i - w'_i |是最小的，其中w_i是边缘i_th的重量和w'_i是边缘i_th的权重改变后。

suppose we are given a weighted graph G and a spanning tree T of it.we want to change weights of edges so that T be a minimum spanning tree and sum of all |w_i - w'_i| be minimum where w_i is the weight of edge i_th and w'_i is the weight of edge i_th after changing it.

我觉得很明显我们的目标是尽量减少金额| w_i - w'_i |对所有的i和我们的变量是w'_i，但我无法找到如何重新present T是最小约束生成树。

I think it's obvious our goal is to minimize sum of |w_i - w'_i| for all i and our variables are w'_i but i can't find how to represent T is minimum spanning tree in constrains.

推荐答案

对于每一个我，使我日边缘不T中，对每个j，使得第j 个边缘位于T中的唯一路径从第i 个边缘到另一个的一个端点，还有一个约束瓦特我' - 瓦特Ĵ ≥0。

For each i such that the ith edge is not in T, for each j such that the jth edge lies on the unique path in T from one endpoint of the ith edge to the other, there is a constraint wi' - wj' ≥ 0.