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整數對象，從而提高了性能。