사용자 도구

사이트 도구


ps:problems:boj:6497

전력난

ps
링크acmicpc.net/…
출처BOJ
문제 번호6497
문제명전력난
레벨골드 4
분류

최소 신장 트리

시간복잡도O(T*ElogV)
인풋사이즈T<=?, V<=200,000, E<=200,000
사용한 언어Python
제출기록95340KB / 1380ms
최고기록1172ms
해결날짜2022/09/29
태그

[라이]최소 스패닝 트리

풀이

  • 불이 켜진 길의 길이가 최소가 되어야 한다. 이것은 최소 신장 트리 (Minimum Spanning Tree / MST) 알고리즘으로 바로 구할수 있다.
  • 문제에서 요구하는 것은 불이 켜진 길의 길이가 아니라, 불이 켜진 길을 제외한 나머지 길의 길이이므로, 전체 길의 길이의 합에서 불이 켜진 길의 길이의 합을 빼주면 된다.
  • 시간복잡도는 최소 신장 트리 (Minimum Spanning Tree / MST)를 구하는데에 드는 O(ElogV)이다.

코드

"""Solution code for "BOJ 6497. 전력난".

- Problem link: https://www.acmicpc.net/problem/6497
- Solution link: http://www.teferi.net/ps/problems/boj/6497

Tags: [Minimum spanning tree]
"""

import sys
from teflib import graph as tgraph


def main():
    while (line := sys.stdin.readline().rstrip()) != '0 0':
        m, n = [int(x) for x in line.split()]
        edges = [
            [int(x) for x in sys.stdin.readline().split()] for _ in range(n)
        ]

        total_cost = sum(z for x, y, z in edges)
        mst_edges = tgraph.minimum_spanning_tree(edges, m)
        mst_cost = sum(z for x, y, z in mst_edges)

        print(total_cost - mst_cost)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q L Q D U
 
ps/problems/boj/6497.txt · 마지막으로 수정됨: 2022/11/07 08:19 저자 teferi