最小生成树 - 题目 - Zijian Online Judge

摩诃萨姆和古德伊特是好朋友。

一天，摩诃萨姆学习了博弈论。当摩诃萨姆完全理解mex运算后，他发出了感叹：“为什么这么巧妙呢？”。

同时，古德伊特遇到了一个最小生成树问题。于是去学习了Borůvka算法，并发出了同样的感叹。

这天，摩诃萨姆向古德伊特普及了他最近新学会的姿势，但是他们之间产生了分歧：摩诃萨姆认为mex问题比最小生成树要难，而古德伊特则坚持最小生成树更难。他们一时争执不下，于是决定询问你的意见。他们将两个问题进行了结合，问题是这样的：

给定一张无向图，每条边有权值，求最小mex生成树，即选出一个生成树，使得边集中权值的mex最小。

其中mex定义为最小未出现自然数，生成树定义为原图中的一个极小连通子图。

为了防止你瞎猜答案，古德伊特决定让你输出选出的所有边。

第一行三个整数 $ n, m, t $ ，分别代表点数、边数和一个没用的数($1 \leq n \leq 200000, 0 \leq m \leq 400000, 1 \leq t \leq 2 $)

接下来 $ m $ 行每行三个正整数 $ u_i, v_i, w_i $ ，代表有一条从 $ u_i $ 连向 $ v_i $ 的边，权值为 $ w_i $ 。保证任意两条边不全相同。

第一行一个正整数，代表求得的最小mex值，若原图不连通输出 $ -1 $

若图连通，则接下来 $ n - 1 $ 行每行输出三个正整数 $ u_i, v_i, w_i $ ，表示生成树中的每条边。

mex函数的取值范围为$[0,\infty)$

1
1 3 0
2 3 0

有三种选取生成树的方案，边集分别为{(1,3,0),(1,2,1)},{(1,2,1),(2,3,0)},{(1,3,0),(2,3,0)}。

显然最后一种方案最优

子任务1 (14 pts): $ 1 \leq n \leq 25, 1 \leq m \leq 25, 0 \leq w \leq 15 $

子任务2 (22 pts): $ 1 \leq n \leq 5000, 1 \leq m \leq 10000, 0 \leq w \leq 5000 $

子任务3 (10 pts): 所有 $ w $ 互不相同

子任务4 (34 pts): 相同权值的边不超过15条

子任务5 (20 pts): 无额外限制

对于全部数据：$1 \leq n \leq 200000, 0 \leq m \leq 400000, 1 \leq t \leq 2, 1 \leq u_i < v_i \leq n $ , $ 0 \leq w_i \leq 200000 $。任意两条边不全相同。

时间限制：$3\texttt{s}$

空间限制：$256\texttt{MB}$

Zijian Online Judge