Custom Min Spanning Tree

カスタムミニマルスパニングツリー

説明

入力データからスパニングツリーを構築することは、これらの3つの基本ルールに従う必要があります。

1. グラフはツリーであり、すべてのノードを含む必要があります。
2. グラフには、それらのエッジに関連するコストに関係なく、特定の長さの最大可能なエッジ数を含める必要があります。
3. 最初と2番目のルールを尊重する結果のグラフのエッジ長の合計を最小限に抑える必要があります。

画像1。グラフノード間の可能な接続のスキーム。可能な接続がエッジとして描かれています。目的のスパニングツリーを形成する可能性のある接続は、赤で強調表示されます。ケースa）、b）、c）以下の例1、2、3に対応しています。場合によっては（例：ケースBおよびC）、複数のスパニングツリーが問題の要求を満たす可能性があります。ただし、そのようなスパニングツリーはすべて同じ総長さを共有しています。ケースa）ルール3の重要性を示しています。ルール2を満たしているが、規則3を満たしていないエッジ（1、5）および（5、4）を含む木が存在します。

タスク

ノードとそれぞれの接続長の間のすべての可能な接続のリストが与えられます。説明に示されている3つのルールすべてを満たすスパニングツリーの全長を計算します。

タスクのデータセットは、チェコ工科大学の教師によって、「高度なアルゴリズム化」のために作成されました。

入力

入力の最初の行は、空間で区切られた2つの整数nとmで構成されています。値nはノードの数です。値mは、ノードのペア間の可能な接続の数です。次に、各行が1つの可能な接続を表すM行があります。ラインには、空間で分離された3つの整数D1、D2、Lが含まれています。つまり、ノードD1とD2の間の可能な接続の長さはLに等しいことを意味します。検出器には1からNから番号が付けられます。可能な接続にはランダムな順序でリストされます。 N≤30000およびM≤300000を保持します。各長さは最大10^9です。

出力

出力は、必要なネットワークの最小合計長を含む1行です。結果は2^60を超えていません。

例1

例1入力データと結果のネットワークは、画像1 a）に示されています。

例2

例2入力データと結果のネットワークは、画像1 bに示されています。

例3

例2入力データと結果のネットワークは、画像1 cに示されています。

解決

タスクは、最適化された組合ファインドアルゴリズムを使用してJavaに実装されます（ここで説明します）。アルゴリズムでは、著者のジャスティン・カウチ、アレックス・チャフィー、スティーブン・コールボーンによって実装されたハッシュマップの修正バージョンが使用されています。このハッシュマップは、原始的な整数のみを使用し、Java整数オブジェクトではなく、パフォーマンスが向上しました。