[BOJ/Gold 2] 백준 20010 악덕 영주 혜유(C++)

문제 링크

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

20010번: 악덕 영주 혜유

 

문제

FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, 교역로는 양 방향으로 이동할 수 있으며, 서로 도달이 불가능한 마을이 없도록 교역로를 건설하여야 한다.

마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 모든 마을과 마을을 최소한의 비용으로 연결하고 그 비용을 구해보자. 또한 혜유는 이때 마을과 마을을 이동하는 가장 최악의 비용이 얼마인지에 관심이 많다. 임의의 두 마을을 이동하는 최단 경로 중 비용이 가장 큰 경로의 비용도 구해보자.

입력

첫 번째 줄에는 마을의 수 N(1 ≤ N ≤ 1,000)과 설치 가능한 교역로의 수 K(1 ≤ K ≤ 1,000,000)가 주어진다.

두 번째 줄부터 K + 1줄에는 서로 다른 두 마을의 번호 a, b (a ≠ b)와 두 마을을 연결하는 비용 c가 주어진다. (1 ≤ c ≤ 1,000,000)

항상 모든 마을을 연결할 수 있는 경우만 입력으로 주어진다, 또한 최소 비용으로 연결하는 방법은 유일하다.

서로 다른 두 마을 사이에 건설할 수 있는 교역로는 최대 하나뿐이다.

마을은 0부터 N - 1 사이의 번호를 갖는다.

출력

첫 번째 줄에는 모든 마을을 연결하는 최소 비용을 출력한다. 

두 번째 줄에는 마을과 마을을 이동하는 비용이 가장 큰 경로의 비용을 출력한다.

예제 입력 1

6 7
0 1 5395
0 2 540
0 4 7096
1 2 1051
2 4 4750
3 4 9616
3 5 9476

예제 출력 1

25433
24893

예제 입력 2

7 9
0 1 4068
0 3 9921
1 4 474
2 3 421
2 5 9685
3 4 1182
3 5 1690
4 6 9761
5 6 644

예제 출력 2

8479
8058

알고리즘 분류

• 크루스칼 알고리즘

풀이

최소 스패닝 트리를 만들어, 가중치의 최솟값을 구한다.

그리고 최단 경로 중 비용이 가장 큰 경로의 비용은 다음과 같이 구한다.

1. 임의의 정점(본인은 0번 정점으로 함)에서 가장 먼 정점을 구하고 비용을 구한다.

2. 그 정점에서 가장 먼 정점을 구하고 비용을 구한다.

3. 두 비용을 합한다.

이렇게 해서 비용이 가장 큰 경로의 비용을 구한다.

코드

#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 1001
#define LL long long
#define INF 1e9

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

int N, K;
int Parent[MAX];
vector<pair<int, LL> > Vec[MAX];
vector<INFO> Edge;
bool visited[MAX];
LL answer = 0;
LL Big = 0;
int CenterNode;

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

void Init2() {
	for (int i = 0; i < N; i++) {
		visited[i] = false;
	}
}

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 Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

void DFS(int X, LL Sum) {
	if (Big < Sum) {
		Big = Sum;
		CenterNode = X;
	}
	for (int i = 0; i < Vec[X].size(); i++) {
		int Next = Vec[X][i].first;
		if (!visited[Next]) {
			visited[Next] = true;
			DFS(Next, Sum + Vec[X][i].second);
		}
	}
}

void Input() {
	cin >> N >> K;
	Init();
	for (int i = 0; i < K; i++) {
		int A, B;
		LL C;
		cin >> A >> B >> C;
		Edge.push_back({ A,B,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;
		LL C = Edge[i].Cost;
		if (Find(S) != Find(E)) {
			Union(S, E);
			answer += C;
			Big = max(Big, C);
			Vec[S].push_back(make_pair(E, C));
			Vec[E].push_back(make_pair(S, C));
		}
	}
	visited[0] = true;
	DFS(0, 0);
	Init2();
	visited[CenterNode] = true;
	DFS(CenterNode, 0);
}

void Find_Answer() {
	cout << answer <<"\n" << Big << "\n";
}

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

	return 0;
}