Custom Min Spanning Tree

커스텀 최소 스패닝 트리

설명

입력 데이터에서 스패닝 트리를 구축하면이 세 가지 기본 규칙에 따라야합니다.

1. 그래프는 트리 여야하고 모든 노드를 포함해야합니다.
2. 그래프는 그 가장자리와 관련된 비용에 관계없이 특정 길이의 최대 가장자리 수를 포함해야합니다.
3. 첫 번째 규칙과 두 번째 규칙에 대한 결과 그래프의 가장자리 길이의 총 합은 최소화되어야합니다.

이미지 1. 그래프 노드 간의 가능한 연결 체계. 가능한 연결은 가장자리로 표시됩니다. 원하는 스패닝 트리를 형성 할 수있는 연결은 빨간색으로 강조 표시됩니다. 사례 a), b), c)는 아래의 예 1, 2, 3에 해당한다. 경우에 따라 (예 : B 및 C의 경우) 둘 이상의 스패닝 트리가 문제 요구를 충족시킬 수 있습니다. 그러나 그러한 모든 스패닝 나무는 같은 총 길이를 공유합니다. 사례 a)는 규칙 3의 중요성을 보여줍니다. 규칙 2를 만족하지만 규칙 3을 만족시키지 않는 가장자리 (1, 5) 및 (5, 4)를 포함하는 나무가있는 나무가 존재합니다.

일

노드와 각 연결 길이 간의 가능한 모든 연결 목록이 제공됩니다. 설명에 제시된 세 가지 규칙을 모두 만족시키는 스패닝 트리의 총 길이를 계산하십시오.

이 작업의 데이터 세트는 체코 기술 대학교 교사들이 '고급 알고리즘'주제에 의해 만들어졌습니다.

입력

입력의 첫 번째 줄은 공간으로 분리 된 2 개의 정수 n과 m으로 구성됩니다. 값 n은 노드 수입니다. 값 M은 노드 쌍 간의 가능한 연결 수입니다. 다음으로 M 라인이 있으며 각 라인은 하나의 가능한 연결을 나타냅니다. 라인에는 공간별로 분리 된 3 개의 정수 D1, D2, L이 포함되어 있으며, 이는 노드 D1과 D2 사이의 가능한 연결 길이가 L과 동일하다는 것을 의미합니다. 검출기는 1에서 N에서 N까지 번호가 매겨집니다. 가능한 연결은 임의 순서로 나열됩니다. N ≤ 30000 및 M ≤ 300000을 유지합니다. 각 길이는 최대 10^9입니다.

산출

출력은 필요한 네트워크의 최소 총 길이를 포함하는 한 줄입니다. 결과는 2^60을 초과하지 않습니다.

예 1

예 1 입력 데이터 및 결과 네트워크는 이미지 1 a에 나와 있습니다.

예 2

예제 2 입력 데이터 및 결과 네트워크는 이미지 1 b)에 도시되어있다.

예 3

예제 2 입력 데이터 및 결과 네트워크는 이미지 1c에 나와 있습니다.

해결책

이 작업은 최적화 된 Union-Find 알고리즘을 사용하여 Java로 구현됩니다 (여기 설명). 알고리즘에는 저스틴 소파 (Justin Couch), 알렉스 샤피 (Alex Chaffee) 및 스티븐 콜레 본 (Stephen Colebourne)이 구현 한 수정 된 해시 맵 버전이 사용됩니다. 이 해시 맵은 Java Integer 객체가 아닌 원시 정수 만 사용하여 성능이 향상되었습니다.