Module: スパニング ツリー: Kruskal のアルゴリズム

Problem

Besi は、1…N とラベル付けされた N (2≤N≤10⁵) 個の頂点と 1…2N とラベル付けされた 2N 個のポータルのネットワーク上にあります。各ポータルは、2 つの異なる頂点 u と v (u≠v) を接続します。ポータルのセットは、いくつかの頂点のペアを接続できます。
各頂点 v は、4 つの異なるポータルに隣接しています。 v のポータルのリストは pv=[p_v,1,p_v,2,p_v,3,p< で与えられますsub>v ,4].

現在の位置は、順序付けられたペア (現在の頂点、現在のポータル) で表すことができます。つまり、1≤v≤N と 1≤i≤4 のペア (v,p_v,i) です。次の操作のいずれかを使用して、現在の位置を変更できます。

現在のポータルを移動して、現在の頂点を変更します。
現在のポータルを切り替えます。各頂点で、リストの最初の 2 つのポータルがペアになり、リストの最後の 2 つのポータルもペアになります。したがって、現在の状態が (v,p_v,2) の場合、ポータル (v,p_v,1) を使用するように切り替えて、元に戻すことができます。同様に、現在の位置が (v,p_v,3) の場合、ポータル (v,p_v,4) に切り替えて戻ることができます。他の切り替えは許可されていません (たとえば、ポータル pv,2 からポータル p_v,4 に切り替えることはできません)。
全部で 4N の異なる状態があります。残念ながら、特定の一連の操作によって任意の状態から任意の状態に到達できるとは限りません。したがって、cv (1≤c_v≤1000) の月のコストで、v に隣接するポータルのリストを任意の順序で並べ替えることができます。その後、リストの最初の 2 つのポータルが 1 つのペアに結合され、最後の 2 つのポータルが別のペアに結合されます。

たとえば、v のポータルを [p_v,3,p_v,1,p_v,2, p_v,4]、これは意味します。あなたがトップvにいる場合はどうなりますか

p_v,1 ポータルにいる場合は、p_v,3 ポータルに切り替えて戻ることができます
p_v,2 ポータルにいる場合は、p_v,4 ポータルに切り替えて戻ることができます
現在、ポータル p_v,1 から p_v,2 へ、またはポータル p_v,3 からポータル p _{へ切り替えることはできません。 v,4} とその逆。
各州から各州に到達できるようにネットワークを変更するために必要な月の最小数を計算します。このようにネットワークを変更する方法が少なくとも 1 つ存在するように、テスト データが構築されていることが保証されています。

入力: 
最初の行には N が含まれています。
次の N 行のそれぞれが頂点を記述します。文字列 v+1 には、スペースで区切られた 5 つの整数 c_v,p_v,1,p_v,2,p_{v が含まれます,3},p_v,4.
各 v に対して、すべて p_v,1,p_v,2,p_v,3,p_{v, 4 つの} は区別され、各ポータルは正確に 2 つの頂点のリストに表示されます。

出力: 
1 つの行には、ネットワークを変更して各州から別の州に到達できるようにするために必要な最小数の衛星が含まれています。
 

例

<頭> <本体>

#	入力	出力	説明
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	頂点 1 と 4 のリストを交換するだけで十分です。これには c1+c4=13 ミリ秒が必要です。順列は、p1=[1,9,4,8​​] および p4=[7,4,6​​,3] です。