luogu#P5631. 最小mex生成树

    ID: 9653 远端评测题 2000ms 500MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>线段树并查集O2优化分治Link-Cut TreeLCT

最小mex生成树

题目背景

这是一道经典题。

题目描述

给定 nn 个点 mm 条边的无向连通图,边有边权。

设一个自然数集合 SSmex\text{mex} 为:最小的、没有出现在 SS 中的自然数。

现在你要求出一个这个图的生成树,使得其边权集合的 mex\text{mex} 尽可能小。

输入格式

第一行输入两个正整数 n,mn,m

接下来 mm 行,每行 33 个非负整数 u,v,wu,v,w,表示 u,vu,v 之间有一条权值为 ww 的边。

输出格式

输出一行一个自然数,表示最小的 mex\text{mex} 值。

3 3
1 2 0
2 3 1
3 2 2

1

提示

【数据范围】

  • 对于 20%20\% 的数据,1n1001\le n \le 1001m2001\le m \le 200
  • 对于 50%50\% 的数据,1n20001\le n \le 20001m30001\le m \le 3000
  • 对于 80%80\% 的数据,1n1051\le n \le 10^51m2×1051\le m \le 2\times 10^5
  • 对于 100%100\% 的数据,1n1061\le n \le 10^61m2×106,0w1051\le m \le 2\times 10^6,0\le w \le 10^5

输入数据规模较大,建议使用高效的读入方式。