推荐边最小生成树(Recommended MST)

题目描述

给定一个包含 $n$ 个顶点、$m$ 条带权无向边的连通图，顶点编号为 $1 \sim n$。

小杨正在学习 Kruskal 最小生成树算法。在原图中，某些边被标记为“推荐边”（$t_i = 1$），其余边为“普通边”（$t_i = 0$）。

请你帮小杨求出：

1. 原图最小生成树的边权之和；
2. 在保证生成树边权之和最小（即仍为最小生成树）的前提下，一棵最小生成树中最多可以包含多少条“推荐边”。

输入格式

第一行包含两个正整数 $n, m$，分别表示顶点数与边数。

接下来 $m$ 行，每行包含四个整数 $u_i, v_i, w_i, t_i$（$t_i \in \{0, 1\}$），分别表示一条连接 $u_i$ 和 $v_i$、权值为 $w_i$、标记为 $t_i$ 的无向边。保证图连通。

输出格式

输出一行两个用空格隔开的整数，分别表示最小生成树的边权之和，以及最小生成树中最多可包含的推荐边数量。

样例输入 #1

4 5
1 2 2 0
2 3 2 1
1 3 2 1
3 4 3 0
1 4 3 1

样例输出 #1

7 3

数据范围

对于 $100\%$ 的数据，$2 \le n \le 10^5$，$n - 1 \le m \le 2 \times 10^5$，$1 \le w_i \le 10^9$，$t_i \in \{0, 1\}$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1500。

测试点分布

出处：原题链接