#o. 「一本通 3.1 练习 4」Tree

Type: Default

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：2012 年国家集训队互测

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 $\text{need}$ 条白色边的生成树。题目保证有解。

第一行 $V,E,\text{need}$ 分别表示点数，边数和需要的白色边数。

接下来 $E$ 行，每行 $s,t,c,\text{col}$ 表示这边的端点（点从 $0$ 开始标号），边权，颜色（ $0$ 白色， $1$ 黑色）。

一行表示所求生成树的边权和。

2 2 1
0 1 1 1
0 1 2 0

对于所有数据， $V\le 5\times 10^4,E\le 10^5$ ，边权为 $[1, 100]$ 中的正整数。