문제

https://www.acmicpc.net/problem/2406

Point

본사(1)를 제외한 지사들이 MST를 이루어야 한다.

• 우선 기본적으로 본사(1)와 모든 지사(노드) 사이에 연결이 다 있기 때문에, 나머지가 MST를 이루면 고장이 발생하더라도 경로가 존재 할 수 있다.

초기 간선

• 초기에 주어진 연결(간선)이 MST의 구성 간선이 아닐 수 있다. 그러므로 초기의 간선도 MST에 무조건 추가하고 시작하면 안되고, union()함수를 이용해서 넣어야 한다.
  

전체 코드

import heapq

n, m = [int(x) for x in input().split()]
par = [x for x in range(n+1)]

def find(x):
  if par[x] == x:
    return x
  else:
    p = find(par[x])
    par[x] = p
    return p
    
def union(a, b):
  p_a = find(a)
  p_b = find(b)
  if p_a == p_b:
    return 0
  else:
    par[p_b] = p_a
    return 1
    
for i in range(m):
  a, b = [int(x) for x in input().split()]
  union(a,b)

cost = [[0] for _ in range(n+1)]
for i in range(1, n+1):
  cost[i] = cost[i]+[int(x) for x in input().split()]

pq = []
for i in range(2, n+1):
  for j in range(2,i):
    if find(i) == find(j):
      continue
    else:
      heapq.heappush(pq, (cost[i][j], i, j))

cost = 0
net = 0
new_net = []
while pq:
  c, a, b = heapq.heappop(pq)
  if union(a,b) == 1:
    cost += c
    new_net.append((a,b))
    net += 1
  if net == n-1:
    break

print(f"{cost} {len(new_net)}")
for a in new_net:
  print(f"{a[0]} {a[1]}")