← 返回题目列表

Codeforces · 1508/C

C. 完成 MST

中文机器翻译题面 查看原题

作为一名老师,Riko Hakozaki 经常需要帮助她的学生解决各个科目的问题。今天,她被要求完成一项编程任务,内容如下。

给您一个带有 $$$n$$$ 个节点的无向​​完整图,其中一些边预先分配了正权重,而其余边则没有。您需要为所有未分配的边分配非负权重,以便在生成的完全分配的完整图中,所有权重的异或总和将等于 $$$0$$$。

将完全分配的完整图的丑陋定义为其最小生成树的权重,其中生成树的权重等于其边的权重之和。您需要分配权重,以使结果图表的丑陋程度尽可能小。

提醒一下,具有 $$$n$$$ 节点的无向​​完全图包含所有边 $$$(u, v)$$$ 且 $$$1 \le u < v \le n$$$;这样的图有 $$$\frac{n(n-1)}{2}$$$ 边。

她不确定如何解决这个问题,所以她请你帮她解决。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2} - 1)$$$) — 节点数和预分配边数。给出输入以便至少有一个未分配的边。

以下 $$$m$$$ 行中的第 $$$i$$$ 包含三个整数 $$$u_i$$$、$$$v_i$$$ 和 $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u \ne v$$$, $$$1 \le w_i < 2^{30}$$$),表示从$$$u_i$$$到$$$v_i$$$的边已预先分配了权重$$$w_i$$$。输入中没有边出现多次。

输出

在一行上打印一个整数——异或和等于 $$$0$$$ 的所有权重分配中最丑陋的。

示例

输入 #1

4 4
2 1 14
1 4 14
3 2 15
4 3 8

输出 #1

15

输入 #2

6 6
3 6 4
2 4 1
4 5 7
3 4 10
3 5 1
5 2 15

输出 #2

0

输入 #3

5 6
2 3 11
5 3 7
1 4 10
2 4 14
4 3 8
2 5 6

输出 #3

6

注意

下图展示了第一个测试用例。黑色权重是从语句中预先分配的,红色权重是我们分配的,最小生成树由蓝色边缘表示。