1647: 도시 분할 계획

문제 링크

1647: 도시 분할 계획

구현 방식

• 입력으로 주어지는 edges는 모든 노드들이 연결되어있는 간선들이다
• 우선 MST를 구해준 후에, MST의 간선 중 가중치가 가장 큰 간선을 제거해주는 방식으로 유지비 합의 최솟값을 구해주었다
  • MST를 구하는 과정에서, path(MST의 간선들을 저장)도 같이 구해준다
  • path를 cost 기준으로 오름차순 정렬하여 total_cost - path[-1][2]를 출력

코드

import sys
from itertools import combinations

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a = find(a); b = find(b)
    if a < b: parent[b] = a
    else: parent[a] = b

N, M = map(int, sys.stdin.readline()[:-1].split())
edges = []
for m in range(M):
    A, B, C = map(int, sys.stdin.readline()[:-1].split()); edges.append((A, B, C))
edges.sort(key=lambda x:x[2])

tc = 0; path = []
parent = [n for n in range(N+1)]
for i in range(M):
    u, v, c = edges[i]
    if find(u) != find(v):
        tc += c; union(u, v)
        path.append((u, v, c))
path.sort(key=lambda x:x[2])
print(tc - path[-1][2]) #MST의 total cost에서 가중치가 가장 큰 edge를 뺌