문제 링크 : www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 문제를 자세히 읽지 않는다면 최소 스패닝 트리(MST) 문제로 혼동할 수 있다. 제시된 조건 중, "따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다." 라는 내용이 있기 때문에 이 문제는 최소 스패닝 트리로 해결할 수 없게 된다. 다음과 같은 반례를 들 수 있다. 그림에서 붉은 색으..