t_도시분할계획_300

문제

n개의 마을, m개의 길 길양방향가능
길유지비가있음
마을을 분할하고싶음
각분리된마을한의 집들끼리 연결되어있어야함 마을에는 집이하나이상
길도 필요없는 건 없어고 비용을 줄이쉠

답

처음엔문제가 이해가 안됏다 각마을에서 집들끼리는 최소하나의 길이있어야한다는건 이해했지만
연결된 집합들이 원래 두개로 나뉘어지는 것으로 이해했다.
But 항상 한뭉텅이고 내가 길하나를 없애서 두개의 그룹으로 만드는 것같다

input = input.strip().split('\n')
n,m = map(int, input[0].split())

edges = []

for i in range(1, m+1):
    a, b, c = map(int, input[i].split())
    edges.append((c,a,b))
    
edges.sort()

parents = []
for i in range(n+1):
    parents.append(i)

def find_parent(parents,v):
    if parents[v] != v:
        parents[v] = find_parent(parents,parents[v])
    return parents[v]

sum = 0
max_r = -1
for e in edges:
    c,a,b = e
    pa = find_parent(parents,a)
    pb = find_parent(parents,b)
    if pa != pb :
        sum += c
        if max_r < c:
            max_r = c
        if pa < pb:
            parents[pb]=pa
        else:
            parents[pa]=pb

print(sum - max_r)

가장 마지막꺼가 cost가 당연히 젤클꺼기에(sort했잔슴;;)
비교가 필요없다..