테페리넷

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

====== 최소 스패닝 트리 ======

===== 풀이 =====
  * 문제 제목 그대로 [[ps:최소 신장 트리]]를 구하기만 하면 되는 문제.
  * 그래프에 음수 가중치가 있지만 따로 신경쓸 필요는 없다. Prim 알고리즘과 Kruskal 알고리즘 모두 음수 가중치의 존재여부에 관계 없이 정상적으로 동작한다.
  * 시간복잡도는 O(ElogV)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1197. 최소 스패닝 트리".

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

Tags: [MST]
"""

import sys
from teflib import tgraph


def main():
    V, E = [int(x) for x in sys.stdin.readline().split()]
    edges = []
    for _ in range(E):
        A, B, C = [int(x) for x in sys.stdin.readline().split()]
        edges.append((C, A - 1, B - 1))

    print(tgraph.minimum_spanning_tree_from_edges(V, edges))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:tgraph#minimum_spanning_tree_from_edges|teflib.tgraph.minimum_spanning_tree_from_edges]]

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