⚠︎ 백준 - 6469 전력난⚡️

최소 신장 트리 단계를 끝내자~2

최소 신장 트리 단계

---

6469

 

⚠︎ 전력난

티어 : 🥇4

분류 : 최소 신장 트리

 

 

 

os 업데이트하니까 이모티콘 추천도 해주네

⚡️⚡️⚡️⚡️⚡️⚡️⚡️

 

엇 문제에 성진이가 나온다.

훈련소에서 잘 살기를...

 

import sys

#유파
def find(v):
    if parents[v] != v:
        parents[v] = find(parents[v])
    return parents[v]
def union(a,b):
    a = find(a)
    b = find(b)
    parents[a] = b


# 집 / 길
M, N = map(int,sys.stdin.readline().split())

# 길
loads = []
total_money = 0
for _ in range(N):
    a, b,d = map(int,sys.stdin.readline().split())
    total_money += d
    loads.append((d,a,b))
loads.sort(reverse = True)

# 부모 초기화
parents = []
for i in range(M):
    parents.append(i)

# 본게임
light_on_road = 0
light_on_lamp = 0
while(light_on_road < M-1):
    d, a, b = loads.pop()
    if (find(a) != find(b)):
        union(a,b)
        light_on_lamp += d
        light_on_road += 1

print(total_money - light_on_lamp)

 

아니 요즘 마가 꼈나 또 틀렸다한번에 맞지를 않아

 

 

 

..아니 이런 쓰레기같은문제!

입력은 여러 개의 테스트 케이스로 구분되어 있다.

로 테케가 있다고 말하면 어떡해!

입력 맨 앞에 T 이런 거 있게 만들었어야지!

ㅎㅏ다못해 예제도 여러 개 테케로 해 주든가!

 

0 0이 왜 있나 했더니..문제 잘 읽어야겠다...

import sys

#유파
def find(v):
    if parents[v] != v:
        parents[v] = find(parents[v])
    return parents[v]
def union(a,b):
    a = find(a)
    b = find(b)
    parents[a] = b

while(True):
    # 집 / 길
    M, N = map(int,sys.stdin.readline().split())
    if (M==0 and N==0):
            break
    # 길
    loads = []
    total_money = 0
    for _ in range(N):
        a, b,d = map(int,sys.stdin.readline().split())
        total_money += d
        loads.append((d,a,b))
    loads.sort(reverse = True)
    
    # 부모 초기화
    parents = []
    for i in range(M):
        parents.append(i)
    
    # 본게임
    light_on_road = 0
    light_on_lamp = 0
    while(light_on_road < M-1):
        d, a, b = loads.pop()
        if (find(a) != find(b)):
            union(a,b)
            light_on_lamp += d
            light_on_road += 1
    
    print(total_money - light_on_lamp)

다시정통공이랑싸우러20000...

버블티를먹을까말까