고속철도망 설계하기
시간 제한2초메모리 제한128 MB
이미 놓인 철도(음수 값)는 반드시 포함하면서 전체 도시를 연결하는 최소 신장 트리 비용과 새로 건설할 노선을 구하는 문제입니다.
문제
N개의 도시가 있는 나라에서 모든 도시가 고속철도망으로 서로 연결되도록 하려고 한다.
일부 도시 쌍에는 이미 고속철도가 설치되어 있다. 이미 설치된 노선은 철거하지 않으며, 그 비용도 전체 사업 비용에 포함한다. 아직 연결되지 않은 도시 쌍에는 주어진 비용을 내고 새 고속철도를 설치할 수 있다.
새 노선을 적절히 추가하여 임의의 도시에서 다른 임의의 도시로 고속철도만 이용해 이동할 수 있게 만들 때, 전체 비용의 최솟값과 새로 설치한 노선들을 구하라.
입력
첫째 줄에 도시의 수 N이 주어진다. (1 <= N <= 200)
다음 N개의 줄에는 N개의 정수가 주어지며, 이는 도시 쌍 사이의 비용을 나타내는 인접행렬이다. 각 비용의 절댓값은 10,000을 넘지 않는다. 두 도시 사이의 값이 음수이면 그 두 도시 사이에는 이미 고속철도가 설치되어 있으며, 그 비용은 해당 값의 절댓값이다. 양수이면 아직 설치되지 않았고, 그 값을 비용으로 내면 새 노선을 설치할 수 있다.
출력
첫째 줄에 두 정수 C와 M을 출력한다. C는 이미 설치된 고속철도와 새로 설치한 고속철도를 모두 포함한 최소 총비용이고, M은 새로 설치한 고속철도의 개수이다.
다음 M개의 줄에는 새로 고속철도를 설치한 두 도시 번호를 한 줄에 하나씩 출력한다.