N 個のノードと N-1 個の接続リンクを持つコンピュータ ネットワークがあります。各接続リンクには時間が関連付けられています。
図に示すように、初期ネットワーク設定が与えられます。コンピュータは双方向リンクで接続されています。
ネットワーク時間は、ノード (コンピューター) の任意のペア間の時間の最大値として定義されます。
この図では、ネットワーク時間は 25 です (ノード 5、2、3、6)。
私たちのタスクは、正確に 1 つのエッジを削除し、このエッジを別の場所に追加することによって、このネットワーク時間を最大化することです。状態は:
1.エッジの一方または両方の端を削除して追加できます。
2. この操作の後、ネットワークはスパニング ツリーになり、頂点の各ペア間にパスが 1 つだけ存在します。
上記のネットワークは、次の図のように変換して、最大ネットワーク時間を 25 にすることができます。
制約は次のとおりです。N、コンピューター (ノード) の数は 4 ～ 2000 です。 望ましい: (C および C++) の実行時間が 1 秒の最適解。
