문제 링크

https://www.luogu.org/problemnew/show/P3366

문제 설명

주어진 무방향 그래프의 최소 신장 트리를 구하시오. 만약 그래프가 연결되지 않은 경우, "orz"를 출력하십시오.

입출력 형식

입력 형식:

첫 번째 줄에는 두 개의 정수 N, M이 포함되며, 이는 그래프에 총 N개의 정점과 M개의 무방향 간선이 있음을 나타냅니다. (N <= 5000, M <= 200000)

다음 M줄에는 각 줄에 세 개의 정수 Xi, Yi, Zi가 포함되며, 이는 길이가 Zi인 무방향 간선이 정점 Xi와 Yi를 연결함을 나타냅니다.

출력 형식:

하나의 숫자를 출력하며, 이는 최소 신장 트리의 모든 간선 길이의 합입니다. 만약 그래프가 연결되지 않은 경우 "orz"를 출력합니다.

입출력 예

입력 예:``` 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3

**출력 예:**```
7

설명

시간 및 메모리 제한: 1000ms, 128M

데이터 규모:

20%의 데이터: N <= 5, M <= 20

40%의 데이터: N <= 50, M <= 2500

70%의 데이터: N <= 500, M <= 10000

100%의 데이터: N <= 5000, M <= 200000

예시 설명:

최소 신장 트리의 총 간선 가중치는 2+2+3=7입니다.

해결 방법

이것은 그래프의 최소 신장 트리를 찾는 문제입니다. 최소 신장 트리에 대한 기본 지식이 부족하다면 다른 블로그를 참조하십시오: https://www.cnblogs.com/yinyuqin/p/10779387.html

여기서는 크러스칼 알고리즘에 대해 설명합니다.

장점은 무엇인가요?

• 그래프를 구축할 필요가 없습니다
• 프림 알고리즘에 비해 더 유연합니다

주요 아이디어:

먼저, 각 간선을 구조체에 저장하고, 간선을 가중치에 따라 오름차순으로 정렬합니다. 그런 다음 각 간선을 차례대로 확인하고, 연결된 두 정점이 연결되어 있지 않으면 최소 신장 트리에 추가합니다. 이렇게 하면 먼저 추가되는 간선이 항상 가중치가 가장 작은 간선이 됩니다.

이 과정을 어떻게 구현하나요?

우리는 유지 관리를 위해 분리 집합(Disjoint Set)을 사용할 것입니다. 분리 집합을 사용하여 각 간선이 연결하는 두 정점이 연결되어 있는지 확인하고, 그렇지 않으면 이 두 집합을 병합합니다. 이렇게 하면 최소 신장 트리를 빠르게 구축할 수 있습니다.

이 문제에서 그래프가 연결되어 있는지 확인하는 또 다른 방법은 마지막 최소 신장 트리에 n-1개의 간선만 있는지 확인하는 것입니다. 왜냐하면 n개의 정점을 가진 트리는 n-1개의 간선을 가지기 때문입니다. 데이터가 충분히 쉬워서 확인하지 않아도 정답을 받을 수 있습니다!

아래 코드를 참조하십시오.

 1 #include<iostream>
 2 #include<algorithm>        //sort 헤더 파일 
 3 using namespace std;
 4 struct Edge{            //구조체로 각 간선 저장 
 5     int start;
 6     int end;
 7     int weight;
 8 }edges[200005]; 
 9 int vertexCount, edgeCount, selectedEdges, totalWeight, parent[5005];//selectedEdges는 선택된 간선 수, totalWeight는 최소 신장 트리의 간선 가중치 합 
10 bool compare(Edge a, Edge b){ //sort 비교 함수 (구조체이므로) 
11     return a.weight < b.weight;
12 }
13 int find(int x){            //분리 집합에서 x의 조상 찾기 
14     if(parent[x] == x) return x;
15     return parent[x] = find(parent[x]);//경로 압축 
16 }
17 int main()
18 {
19 cin >> vertexCount >> edgeCount;
20 for(int i = 1; i <= vertexCount; i++) parent[i] = i;    //분리 집합: 처음에는 각 정점의 조상을 자기 자신으로 설정 
21 for(int i = 1; i <= edgeCount; i++){
22     cin >> edges[i].start >> edges[i].end >> edges[i].weight;
23 }
24 sort(edges + 1, edges + edgeCount + 1, compare);    //오름차순 정렬 
25 for(int i = 1; i <= edgeCount; i++){
26     int node1 = edges[i].start;
27     int node2 = edges[i].end;
28     int root1 = find(node1);        //시작점과 끝점의 조상 각각 찾기 
29     int root2 = find(node2);
30     if(root1 != root2){                //시작점과 끝점이 연결되어 있는지 확인 
31         selectedEdges++;                //연결되어 있지 않으면 이 간선을 최소 신장 트리에 추가 
32         totalWeight += edges[i].weight;     
33         parent[root1] = root2;            //두 정점 연결 
34     }
35 }
36 if(selectedEdges != vertexCount - 1){            //selectedEdges != vertexCount-1이면 이 그래프는 연결 그래프가 아님 
37     cout << "orz" << endl;
38     return 0;
39 }
40 cout << totalWeight;
41 return 0;
42 }

AC 코드