Module: 스패닝 트리: Kruskal의 알고리즘

Problem

Besi는 1…N으로 표시된 N(2≤N≤10⁵) 정점과 1…2N으로 표시된 2N 포털의 네트워크에 있습니다. 각 포털은 서로 다른 두 정점 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)입니다. 다음 작업 중 하나를 사용하여 현재 위치를 변경할 수 있습니다.

현재 포털을 통해 이동하여 현재 정점을 변경합니다.
현재 포털을 전환합니다. 각 정점에서 목록의 처음 두 포털이 쌍을 이루고 목록의 마지막 두 포털도 쌍을 이룹니다. 따라서 현재 상태가 (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에 인접한 포털 목록을 원하는 순서대로 재정렬할 수 있습니다. 그런 다음 목록의 처음 두 포털이 한 쌍으로 결합되고 마지막 두 포털이 다른 쌍으로 결합됩니다.

예를 들어 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} 및 그 반대.
각 상태에서 각 상태에 도달할 수 있도록 하는 방식으로 네트워크를 수정하는 데 필요한 달의 최소 수를 계산합니다. 이러한 방식으로 네트워크를 수정할 수 있는 방법이 적어도 한 가지 이상 있는 방식으로 테스트 데이터가 구성되어 있음을 보장합니다.

입력: 
첫 번째 줄에는 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개의} 는 고유하며 각 포털은 정확히 두 개의 정점 목록에 나타납니다.

출력: 
한 줄에는 다른 상태에서 각 상태에 도달할 수 있도록 네트워크를 수정하는 데 필요한 최소 달 수가 포함되어 있습니다.
 

예

<헤드> <몸>

#	입력	출력	설명
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]입니다.