P4412 [SHOI2004] Minimum Spanning Tree

Given a simple graph $G=\langle V, E, W \rangle$, where $V$ is the set of vertices, $E$ is the set of edges (no multiple edges; i.e., there is at most one edge between any two vertices), and $W$ is an integer-valued weight function defined on $E$. A spanning tree $T$ on $G$ is given. Modify $W$ with the minimum total cost so that $T$ becomes a minimum spanning tree on $G$ (a graph may have multiple minimum spanning trees; it suffices that the sum of edge weights of $T$ is minimum). For any edge $e \in E$, the modification rules are: - Increase the weight of $e$: set $W'(e) = W(e) + \Delta(e)$, and the cost to modify this edge is $\Delta(e)$. - Decrease the weight of $e$: set $W'(e) = W(e) - \Delta(e)$, and the cost to modify this edge is $\Delta(e)$. - Do not change the weight of $e$: set $W'(e) = W(e)$, with modification cost $\Delta(e)=0$. Note: The modified weight function $W'$ also takes integer values. The total modification cost is $S = \sum\limits_{e \in E} \Delta(e)$.

The first line contains $N, M$, where $N$ is the number of vertices and $M$ is the number of edges. Vertices are numbered $1, 2, 3, \dots, N-1, N$. The next $M$ lines each contain three integers $U_i, V_i, W_i$, indicating there is an edge between vertices $U_i$ and $V_i$ with weight $W_i$. Each edge appears exactly once in the input. Then, the next $N-1$ lines each contain two integers $X_i, Y_i$, indicating that the edge between $X_i$ and $Y_i$ is an edge of $T$.

Output the minimum $S$.

Edge $(4,6)$ has its weight changed from $7$ to $3$, with cost $4$; edge $(1,2)$ has its weight changed from $2$ to $3$, with cost $1$; edge $(1,5)$ has its weight changed from $1$ to $4$, with cost $3$. Therefore, the total cost is $4+1+3=8$. Constraints: $1 \le N \le 50$, $1 \le M \le 1500$, $1 \le W_i \le 1000$. Translated by ChatGPT 5