백준 1833 - 고속철도 설계하기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1833

1833번: 고속철도 설계하기

최소 스패닝 트리를 이용한 문제입니다.

미리 연결된 도로들이 주어질 때, 남은 도로들로 모든 도시를 연결하려고 합니다.
이때의 연결된 도로 비용의 최솟값과 어떤 도로들이 추가로 연결되었는지를 출력해주면 됩니다.



자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;

int N;
typedef struct info{
	int x;
	int y;
	int cost;
}info;
vector<info> connect;
vector<pair<int, int>> line;
int parent[201];
int sum_cost;

void reset_parent(){
	for(int i = 1; i <= N; i++){
		parent[i] = i;
	}
}

bool cmp(info a, info b){
	if(a.cost < b.cost) return true;
	else return false;
}

void Union(int x, int y){
	if(x == y) return;
	if(x < y) parent[x] = y;
	else parent[y] = x;
}

int Find(int x){
	if(x == parent[x]) return x;
	else return parent[x] = Find(parent[x]);
}

void solve(){
	sort(connect.begin(), connect.end(), cmp);
	for(int i = 0; i < connect.size(); i++){
		int x = Find(connect[i].x);
		int y = Find(connect[i].y);
		if(x != y){
			Union(x , y);
			sum_cost += connect[i].cost;
			line.push_back({connect[i].x, connect[i].y});
		}
	}
	cout << sum_cost << " " << line.size() << "\n";
	for(int i = 0; i < line.size(); i++){
		cout << line[i].first << " " << line[i].second << "\n";
	}  
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	reset_parent();
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
			int cost;
			cin >> cost;
			if(cost < 0){
				if(i < j){
					sum_cost += -cost;
					Union(Find(i), Find(j));
				}
			}
			else if(cost > 0){
				connect.push_back({i, j, cost});
			}
		}
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.