테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 전력난 ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:graph#minimum_spanning_tree|teflib.graph.minimum_spanning_tree]]

{{tag>BOJ ps:problems:boj:골드_3}}