[BOJ/Gold 3] 백준 32339 대동여지도(C++)

문제 링크

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

 

문제

세종이는 조선 시대의 지도인 대동여지도를 보면서 한양을 포함한 모든 지역을 연결하는 도로를 설치한다면 비용이 얼마나 들지 궁금해졌다.

설치할 수 있는 도로의 종류는 총 3가지로 도보 전용 도로, 말 전용 도로, 마차 전용 도로가 있다.

세종이는 지역을 연결할 수 있는 모든 도로를 전부 설치하고 싶지만 국고가 부족한 관계로 최소한의 비용을 사용하여 모든 지역을 이동할 수 있도록 도로를 설치하려 한다. 만약 최소한의 비용으로 도로를 설치할 수 있는 경우가 여러가지라면, 조정에서 지정해준 우선순위가 1번째인 도로가 가장 많은 순으로, 이 경우도 여러가지라면 우선순위가 2번째인 도로가 가장 많은 순으로 설치하려 한다.

세종이를 도와 최소한의 비용을 사용하여 모든 지역을 연결하는 도로를 설치하고, 설치에 드는 총 비용과 도보, 말, 마차 전용 도로 각각의 설치 개수와 비용을 파악해보자.

 

입력

첫 번째 줄에 장소의 개수 N과 설치할 수 있는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 10,000; N−1 ≤ M ≤ 200,000)

두 번째 줄에 서로 다른 도로 종류 pi가 우선순위가 높은 순서대로 3개 주어지며, 각각 0은 도보 전용 도로, 1은 말 전용 도로, 2는 마차 전용 도로를 의미한다. (0 ≤ pi ≤ 2)

다음 M개의 줄에 걸쳐 두 장소를 연결하는 경로의 정보 ui, vi, wi, ki가 주어진다.

 ui, vi는 각각 지역 번호를 의미한다. (ui ≠ vi; 1 ≤ ui, vi ≤ N)

 wi는 도로의 설치 비용을 의미한다. (1 ≤ wi ≤ 10,000)

 ki는 도로의 종류를 의미하며, 각각 0은 도보 전용 도로, 1은 말 전용 도로, 2는 마차 전용 도로를 의미한다. (0 ≤ ki ≤ 2)

입력은 모든 지역을 연결할 수 있도록 주어진다.

 

출력

첫 번째 줄에 N개의 지역이 연결하기 위해 도로를 설치할 때 필요한 최소 비용을 출력한다.

두 번째 줄에 최소 비용으로 도로를 설치할 때 도보 전용 도로의 설치 개수와 비용을 공백으로 구분하여 출력한다.

세 번째 줄에 최소 비용으로 도로를 설치할 때 말 전용 도로의 설치 개수와 비용을 공백으로 구분하여 출력한다.

네 번째 줄에 최소 비용으로 도로를 설치할 때 마차 전용 도로의 설치 개수와 비용을 공백으로 구분하여 출력한다.

 

예제 입력 1

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

예제 출력 1

7
2 3
1 1
1 3

예제 입력 2

5 30
0 1 2
1 3 3 0
1 3 16 1
1 3 10 2
2 3 16 0
2 3 15 1
2 3 15 2
5 4 6 0
5 4 13 1
5 4 9 2
3 4 13 0
3 4 3 1
3 4 4 2
5 2 13 0
5 2 16 1
5 2 12 2
5 3 7 0
5 3 16 1
5 3 1000 2
2 5 7 0
2 5 1 1
2 5 13 2
3 2 1 0
3 2 3 1
3 2 4 2
1 3 16 0
1 3 1 1
1 3 8 2
2 4 3 0
2 4 7 1
2 4 1 2

예제 출력 2

4
1 1
2 2
1 1

 

알고리즘 분류

• 크루스칼 알고리즘

 

풀이

간선을 정렬할 때, 설치 비용이 동일한 경우에는 우선 순위가 더 먼저인 간선이 앞으로 오도록 한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
#define MAX 10001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct EDGE {
	int U, V, W, K;
};

int N, M, P;
unordered_map<int, int> Priorities;
vector<EDGE> Edges;
int Parent[MAX];
int Answer;
vector<pair<int, int> > Roads(3);

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

void input() {
    cin >> N >> M;
	for (int i = 1; i <= 3; i++) {
		cin >> P;
		Priorities.insert(make_pair(P, i));
	}
	Edges.resize(M);
    for (int i = 0; i < M; i++) {
        cin >> Edges[i].U >> Edges[i].V >> Edges[i].W >> Edges[i].K;
    }
}

bool comp(EDGE A, EDGE B) {
	if (A.W == B.W) {
		return (Priorities[A.K] < Priorities[B.K]);
	}

	return (A.W < B.W);
}

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

	return Parent[X] = findParent(Parent[X]);
}

void unionGroup(int X, int Y) {
	int ParentX = findParent(X);
	int ParentY = findParent(Y);

	if (ParentX < ParentY) {
		Parent[ParentY] = ParentX;
	}
	else {
		Parent[ParentX] = ParentY;
	}
}

void settings() {
	sort(Edges.begin(), Edges.end(), comp);
	for (int i = 0; i < M; i++) {
		int From = Edges[i].U;
		int To = Edges[i].V;
		int Cost = Edges[i].W;
		int Type = Edges[i].K;
		if (findParent(From) != findParent(To)) {
			unionGroup(From, To);
			Answer += Cost;
			Roads[Type].first++;
			Roads[Type].second += Cost;
		}
	}
}

void printAnswer() {
	cout << Answer << "\n";
	for (int i = 0; i < 3; i++) {
		cout << Roads[i].first << " " << Roads[i].second << "\n";
	}
}

int main() {
    FASTIO
    
    init();
    input();
    settings();
    printAnswer();

    return 0;
}