[BOJ/Gold 4] 백준 21924 도시 건설(C++)

문제 링크

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

21924번: 도시 건설

문제

채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다.

공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다.

채완이는 공사하는 데 드는 비용을 아끼려고 한다. 

모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다.

위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도이다.

그림에 있는 도로를 다 설치할 때 드는 비용은 62이다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35이다.

채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다.

채완이를 대신해 얼마나 절약이 되는지 계산해주자.

입력

첫 번째 줄에 건물의 개수 N(3≤N≤105)와 도로의 개수 M(2≤M≤min(N(N−1)2,5×105))가 주어진다.

두 번째 줄 부터 M+1줄까지 건물의 번호 a, b(1≤a,b≤N,a≠b)와 두 건물 사이 도로를 만들 때 드는 비용 c(1≤c≤106)가 주어진다. 같은 쌍의 건물을 연결하는 두 도로는 주어지지 않는다.

출력

예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다.

예제 입력 1

7 9
1 2 15
2 3 7
1 3 3
1 4 8
3 5 6
4 5 4
4 6 12
5 7 1
6 7 6

예제 출력 1

35

위에서 설명한 것과 같다.

예제 입력 2

8 10
1 2 4
2 3 9
2 4 9
3 4 4
3 5 1
4 6 14
6 7 5
5 7 3
7 8 7
6 8 3

예제 출력 2

30

예제 입력 3

5 4
1 2 1
2 3 1
3 1 1
4 5 5

예제 출력 3

-1

알고리즘 분류

• 크루스칼 알고리즘

풀이

최소 스패닝 트리를 만들어 모든 건물을 연결하는 데 드는 최소의 비용을 구하는 문제이다.

모든 건물이 연결되었는 지 확인할 때는 모든 정점의 Parent가 1번 정점인지를 확인하면 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Start, End, Cost;
};

int N, M;
vector<INFO> Edge;
int Parent[MAX];
LL All_Cost = 0;
LL answer = 0;

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

bool Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX < PY) {
		Parent[PY] = PX;
	}
	else {
		Parent[PX] = PY;
	}
}

bool isConnected() {
	for (int i = 2; i <= N; i++) {
		if (Find(1) != Find(i)) {
			return false;
		}
	}
	return true;
}

void Input() {
	cin >> N >> M;
	Init();
	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		Edge.push_back({ A,B,C });
		All_Cost += C;
	}
}

void Settings() {
	sort(Edge.begin(), Edge.end(), Comp);
	for (int i = 0; i < Edge.size(); i++) {
		int S = Edge[i].Start;
		int E = Edge[i].End;
		int C = Edge[i].Cost;
		if (Find(S) != Find(E)) {
			Union(S, E);
			answer += C;
		}
	}
}

void Find_Answer() {
	if (isConnected()) {
		cout << All_Cost - answer << "\n";
	}
	else {
		cout << -1 << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}