algorithm'''problem solve
[백준] 1647 - 도시 분할 계획(Minimum Spanning Tree)
JunHwa Park
2020. 9. 22. 14:45
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
parent = [i for i in range(n + 1)]
edges = list()
def find_parent(c):
if parent[c] != c:
parent[c] = find_parent(parent[c])
return parent[c]
def union(a, b):
ap, bp = find_parent(a), find_parent(b)
if ap < bp:
parent[bp] = ap
else:
parent[ap] = bp
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((c, a, b))
edges.sort()
cost = 0
for edge in edges:
c, a, b = edge
if find_parent(a) != find_parent(b):
last = c
cost += c
union(a, b)
print(cost - last)
|
cs |
https://www.acmicpc.net/problem/1647
1647번: 도시 분할 계획
첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집
www.acmicpc.net
간단한 MST 문제이다.
주의할 점은, 도시를 둘로 나눈다고 했으니 MST의 가장 비용이 비싼 간선은 제외해서 연결을 끊어야한다. (n - 2개의 간선만 연결)