Custom Min Spanning Tree

自定义最小生成树

描述

从输入数据构建生成树应遵守这三个基本规则：

1. 该图必须是树并包含所有节点。
2. 该图应包含一些特定长度的最大可能的边缘数量，而与这些边缘相关的成本如何。
3. 应将尊重第一条规则和第二个规则的结果图的边缘长度总和最小化。

图1。图节点之间可能连接的方案。可能的连接被描述为边缘。可能形成所需的跨越树的连接以红色突出显示。案例a），b），c）对应于下面的示例1、2、3。在某些情况下（例如，在B和C中）多个跨树可能满足问题的需求。但是，所有这些跨越树的共享总长度相同。案例a）说明了规则3的重要性。跨越了包含边缘（1，5）和（5，4）的树，这些树满足规则2但不满足规则3，因为其中任何一个的总长度至少为17。

任务

给出了节点与各个连接长度之间所有可能的连接的列表。计算满足描述中所有三个规则的生成树的总长度。

该任务的数据集是由捷克技术大学的教师创建的，该学科是“高级算法”。

输入

输入的第一行由两个整数N和M组成，这些整数由空间隔开。值n是节点的数量。值m是对节点对之间可能连接的数量。接下来，有M线，其中每行代表一个可能的连接。该线包含三个整数D1，D2，L被空间隔开，这意味着节点D1和D2之间可能连接的长度等于L。检测器编号为1到N。可能的连接以随机顺序列出。它保持N≤30000和M≤300000。每个长度最多为10^9。

输出

输出是包含所需网络的最小总长度的一条线。结果不大于2^60。

示例1

示例1输入数据和结果网络在图像1 a）中描述。

示例2

示例2输入数据和结果网络在图像1 b）中描述。

示例3

示例2输入数据和结果网络在图像1 c中描述。

解决方案

该任务是在Java中使用优化的Union-Find算法实现的（此处解释了）。在算法中，使用了作者Justin Couch，Alex Chaffee和Stephen Colebourne实施的Hashmap修改版本。该哈希图仅使用原始整数而不是Java整数对象，从而提高了性能。