P2619 [CTT] Tree I

You are given an undirected, weighted, connected graph. Each edge is colored black or white. Find a minimum-total-weight spanning tree that contains exactly $need$ white edges. It is guaranteed that a solution exists.

The first line contains $V, E, need$, the numbers of vertices, edges, and the required number of white edges. Then follow $E$ lines. Each line contains $s, t, c, col$, denoting the endpoints (vertices are numbered from $0$), the edge weight, and the color ($0$ for white, $1$ for black).

Output one line: the total weight of the required spanning tree.

Constraints: - For $5\%$ of the testdata, $V \le 10$. - For another $15\%$ of the testdata, $V \le 15$. - For $100\%$ of the testdata, $V \le 5 \times 10^4, E \le 10^5$. - All edge weights are positive integers in $[1, 100]$. By WJMZBMR. Translated by ChatGPT 5