P10669 BZOJ3118 Orz the MST

You are given a connected undirected weighted graph. For each edge $i$, based on its original weight, increasing its weight by $1$ costs $a_i$, and decreasing its weight by $1$ costs $b_i$. Now a spanning tree of the graph is specified. Find the minimum total cost needed to modify edge weights so that this spanning tree becomes a minimum spanning tree of the graph.

The first line contains two positive integers $n, m$, representing the number of vertices and edges in the graph. The vertices are numbered from $1$ to $n$. The next $m$ lines each contain $6$ positive integers $u_i, v_i, w_i, \textit{ff}_i, a_i, b_i$, describing an edge $(u_i, v_i)$ with weight $w_i$. Increasing the original weight by $1$ costs $a_i$, and decreasing the original weight by $1$ costs $b_i$. If $\textit{ff}_i$ is $1$, the edge is in the specified spanning tree; if $\textit{ff}_i$ is $0$, it is not. The data guarantees that the edges with $\textit{ff}_i = 1$ form exactly a spanning tree of the original graph. There may be multiple different edges between two vertices, but there are no self-loops.

Output a positive integer, the minimum total cost required.

**Sample Explanation** The optimal plan is: - Increase the weight of edge $(1,4)$ by $2$, cost $6$. - Increase the weight of edge $(3,5)$ by $3$, cost $3$. - Increase the weight of edge $(3,6)$ by $4$, cost $8$. - Decrease the weight of edge $(4,5)$ by $2$, cost $4$. The total cost is $21$. **Constraints** For $100\%$ of the testdata, $1 \leq n \leq 300$, $1 \leq m, w_i, a_i, b_i \leq 1000$. Translated by ChatGPT 5