글 읽기 - 해당 풀이 지적과 반례 부탁드립니다.

youtaek 1년 전 0

tree에 가중치를 기록하고

parent에 현재 노드까지 오기 위해 거친 노드들을 기록한뒤에

가중치가 가장 큰 두개의 합에서 공통된 부모중 가장 큰 값을 두배해서 빼주는 식으로 생각했는데..

어떤부분이 문제일까요?

n = int(input())
tree = [0] * (n + 1)
parent = [set() for _ in range(n + 1)]

for _ in range(n - 1):
    x, y, d = map(int, input().split())
    tree[y] = tree[x] + d
    parent[y].update(parent[x])
    parent[y].add(x)

sorted_tree = sorted([[x, i] for i, x in enumerate(tree)])[::-1]
m = [sorted_tree[0][1], sorted_tree[1][1]]

com = 0
for a in sorted(list(parent[m[0]]))[::-1]:
    if a in parent[m[1]]:
        com = a
        break

print(tree[m[0]] + tree[m[1]] - 2 * tree[com])

chldn323 1년 전 1

반례입니다.

5-2-1-3 -> 13인데 5-2-4 -> 12 가 나온 것 같네요.

어떻게 고쳐야 될지 몰라서 자세한 내용은 말씀 못 드리겠네요..ㅎㅎ

input:
5
1 2 3
1 3 3
2 4 5
2 5 7

answer:
13

youtaek 1년 전 0

감사합니다 접근방식이 잘못된것같네요 ㅠㅠ

큰 도움 됐습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

해당 풀이 지적과 반례 부탁드립니다.

youtaek 1년 전 0

chldn323 1년 전 1

youtaek 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말