P4412 [SHOI2004] 最小生成树

给定一个筒单图 $G=\langle V.E.W\rangle$，$V$ 为顶点集合，$E$ 为边的集合（无重边，即任意两个顶点之间至多只有一条边)，$W$ 为定义在 $E$ 上的权函数（值为整数)。给出其上的一棵生成树 $T$，现在要求用最小的代价修改 $W$，使得 $T$ 是 $G$ 上的一棵最小生成树（一个图可以有多棵最小生成树，只要 $T$ 的边权和最小即可)。对于任意一条边 $e \in E$ 修改方法为： - 增加 $e$ 的权值，即令 $W'(e)=W(e)+\Delta(e)$，则修改该边的代价为 $\Delta(e)$ - 减小 $e$ 的权值，即令 $W'(e)=W(e)-\Delta(e)$，则修改该边的代价为 $\Delta(e)$ - 不改变 $e$ 的权，即 $W'(e)=W(e)$，修改代价为 $\Delta(e)=0$。 请注意：修改后的权函数 $W'$ 的值域也为整数。 总的修改代价记为 $S=\sum\limits_{e \in E} \Delta(e)$。

无

无

边 $(4,6)$ 的权由 $7$ 修改为 $3$，代价为 $4$； 边 $(1,2)$ 的权由 $2$ 修改为 $3$，代价为 $1$； 边 $(1,5)$ 的权由 $1$ 修改为 $4$，代价为 $3$； 所以总代价为 $4+1+3=8$。 $1 \le N \le 50,1 \le M \le 1500,1 \le W_i \le 1000$。