BOJ 14574(헤븐스 키친)풀이

solved.ac 티어 : 플래 5

 

www.acmicpc.net/problem/14574

14574번: 헤븐스 키친

모든 간선을 이어주고 가중치는

로 해준다. 그리고 스패닝 트리를 만들어 준다음에 사용한 간선들을 저장해서 트리를 만든 다음 dfs으로 탐색을 하면서 밑에부터 위로 가면서 출력해주면 된다.

 

import sys
sys.setrecursionlimit(10**9)
m=int(input())
e=[]
def find(a):
    if uf[a]<0:return a
    uf[a]=find(uf[a])
    return uf[a]
def merge(a,b):
    a=find(a)
    b=find(b)
    if a==b:return 0
    uf[b]=a
    return 1
def dfs(x):
    ch[x]=1
    for i in range(len(hj[x])):
        nt=hj[x][i]
        if ch[nt]==0:
            dfs(nt)
            print(x,nt)
l=[list(map(int,input().split())) for i in range(m)]
for i in range(m):
    for g in range(i+1,m):
        e.append([(l[i][1]+l[g][1])//abs(l[i][0]-l[g][0]),i+1,g+1])
e.sort()
#print(e)
rt=0
cnt=0
uf=[-1]*(m+1)
ch=[0]*(m+1)
hj=[[] for i in range(m+1)]
for i in range(len(e)-1,-1,-1):
    if merge(e[i][1],e[i][2]):
        hj[e[i][1]].append(e[i][2])
        hj[e[i][2]].append(e[i][1])
        rt+=e[i][0]
        cnt+=1
        if cnt==m-1:break
print(rt)

dfs(1)