취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1833번 문제인 고속철도 설계하기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/1833 

이미 건설된 고속철도들이 있을 때, (이미 건설된 고속철도들의 건설비용) + (모든 도시들이 연결되게 하기 위한 추가 고속철도 건설비용)을 최소화하는 문제이다.

일부 노드들이 사전에 연결된 상태에서 최소 스패닝 트리(minimum spanning tree)를 구하는 과정을 이어하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int uf[201];

int findf(int x) {
	if (uf[x] == x) return x;
	return uf[x] = findf(uf[x]);
}

int N;
int ans = 0, cnt = 0;
int arr[201][201];
priority_queue<pair<int, pair<int, int>>> pq; // {-비용,{노드,노드}}
vector<pair<int, int>> anspair;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 1; i <= N; i++) uf[i] = i;

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> arr[r][c];
		}
	}
	for (int r = 1; r < N; r++) {
		for (int c = r + 1; c <= N; c++) {
			if (arr[r][c] < 0) {
				ans -= arr[r][c];
				int rr = findf(r), cc = findf(c);
				if (rr != cc) uf[cc] = rr;
			}
			else pq.push(make_pair(-arr[r][c], make_pair(r, c)));
		}
	}

	while (!pq.empty()) {
		int x = pq.top().second.first, y = pq.top().second.second, d = pq.top().first;
		pq.pop();
		int xx = findf(x), yy = findf(y);
		if (xx == yy) continue;
		uf[yy] = xx;
		ans -= d;
		cnt++;
		anspair.emplace_back(make_pair(x, y));
	}

	cout << ans << ' ' << cnt << '\n';
	for (auto p : anspair) {
		cout << p.first << ' ' << p.second << '\n';
	}
}