[BOJ/Gold 2] 백준 10723 판게아 1(C++)

문제 링크

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

10723번: 판게아 1

 

문제

태초에 세계는 n개의 도시와 이들 사이를 잇는 n−1개의 도로로 이루어져 있었다. 각 도시에는 0 이상 n−1 이하의 정수 번호가 붙어 있었다. 각 도로는 양방향으로 통행 가능하며, 양 끝에 서로 다른 두 개의 도시를 연결하고 있었다. 태초에 세계는 임의의 도시에서 출발하여 다른 모든 도시로 한 개 이상의 도로를 통하여 걸어갈 수 있었다. 

지혜를 갖춘 인간들은 어느새 찬란한 문명을 가지게 되었으나, 도시 사이에 새로운 도로를 놓는 일만큼은 어떻게 해도 해낼 수가 없었다.

이를 지켜보던 조물주는 해마다 두 도시를 잇는 도로를 하나씩 추가하기 시작했는데, 동시에 인간들이 새로운 도로를 사용하기에 합당한 지적 능력을 갖추고 있는지가 궁금해졌다. 그래서 인간들에게 아래와 같은 퍼즐 문제를 제시하였다.

매번 도로가 추가되고 나면 모든 도로 중 일부를 선택하여 모든 도시가 서로 직간접적으로 연결되어 있도록 하며,

이때 선택된 도로들의 길이의 합을 최소로 하는 도로의 부분집합을 알아내기.

 

조물주에게 문제를 받은 인간들은, 이 문제를 해결하여 조물주에게 자신들이 도로를 사용하기에 합당한 존재라는 것을 보여주기로 하였다. 만약 문제를 해결하지 못한다면, 인간들에게 실망한 조물주가 어떤 일을 일으킬지 아무도 알 수 없다. 당신은 인간계 대표로서, 조물주가 내린 시련을 이겨내야만 한다!

입력

첫 줄에는 테스트 케이스의 수 T가 정수로 주어진다. 이어서 매 테스트 케이스의 첫 줄에는 도시의 수 n과 도로가 건설된 횟수 m이 공백으로 구분되어 주어진다. 다음 n−1줄에 태초의 세계에 대한 정보가 주어진다. 이 중 i(1≤i≤n−1)번째 줄에는 정수 ui, ci(0≤ui<i,0≤ci≤10,000,000)가 공백으로 구분되어 주어지는데, 이는 i번 도시와 ui번 도시가 길이가 ci인 도로로 연결되어 있다는 뜻이다. 이어서 m개의 줄에 조물주가 새로이 놓은 도로에 대한 정보가 주어진다. 이 중 j(1≤j≤m)번째 줄에는 정수 uj,vj,cj(0≤uj,vj<n,0≤cj≤10,000,000)가 공백으로 구분되어 주어지는데, 이는 조물주가 j번째로 놓은 도로는, uj번 도시와 vj번 도시 사이를 연결하며, 길이가 cj라는 것을 의미한다.

이 문제는 두 개의 부분문제로 이루어져 있다.

1번 문제의 입력은 1≤n,m≤2,000을 만족하며 해결하면 20점을 얻을 수 있다.

2번 문제의 입력은 1≤n,m≤100,000을 만족하며 해결하면 80점을 얻을 수 있다.

10724번: 판게아 2

출력

각 테스트 케이스마다 단 하나의 줄을 출력한다. 이 줄에는 매번 새 도로를 놓았을 때 문제에 대한 답을 모두 XOR한 값을 출력한다.

예제 입력 1

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

예제 출력 1

7

알고리즘 분류

• 크루스칼 알고리즘
• 프림 알고리즘

풀이

N-1개의 도로를 연결한다. 그리고 M개의 도로를 하나씩 설치할 때마다 최소 스패닝 트리를 만들고 구한 가중치의 최솟값끼리 XOR 연산을 진행한다.

코드

// 크루스칼 알고리즘
#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 2001
#define LL long long
#define INF 1e18

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

int T, N, M;
vector<INFO> Edge;
int Parent[MAX];
LL answer;
LL Year_Cost;

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

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 Settings() {
	sort(Edge.begin(), Edge.end(), Comp);
	for (int i = 0; i < Edge.size(); i++) {
		int U = Edge[i].Start;
		int V = Edge[i].End;
		LL C = Edge[i].Cost;
		if (Find(U) != Find(V)) {
			Union(U, V);
			Year_Cost += C;
		}
	}
	answer ^= Year_Cost;
}

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

void Input() {
	cin >> T;
	while (T--) {
		cin >> N >> M;
		answer = 0;
		Edge.clear();
		for (int i = 1; i <= (N - 1); i++) {
			int U;
			LL C;
			cin >> U >> C;
			Edge.push_back({ i,U,C });
		}
		for (int i = 0; i < M; i++) {
			Init();
			int U, V;
			LL W;
			cin >> U >> V >> W;
			Edge.push_back({ U,V,W });
			Settings();
		}
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}

// 프림 알고리즘
#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 2001
#define LL long long
#define INF 1e18

using namespace std;
int T, N, M;
vector<pair<int, LL> > Edge[MAX];
int Parent[MAX];
bool visited[MAX];
LL answer;
LL Year_Cost;

void Init1() {
	for (int i = 0; i < N; i++) {
		Edge[i].clear();
	}
	answer = 0;
}

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

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 Settings() {
	priority_queue<pair<LL, int> > PQ;
	for (int i = 0; i < Edge[0].size(); i++) {
		int Next = Edge[0][i].first;
		LL Dist = Edge[0][i].second;
		PQ.push(make_pair(-Dist, Next));
	}

	visited[0] = true;
	while (!PQ.empty()) {
		LL CurC = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		if (!visited[CurX]) {
			visited[CurX] = true;
			Year_Cost += CurC;
			for (int i = 0; i < Edge[CurX].size(); i++) {
				LL nextC = Edge[CurX][i].second;
				int nextX = Edge[CurX][i].first;
				if (!visited[nextX]) {
					PQ.push(make_pair(-nextC, nextX));
				}
			}
		}
	};
	answer ^= Year_Cost;
}

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

void Input() {
	cin >> T;
	while (T--) {
		cin >> N >> M;
		Init1();
		for (int i = 1; i <= (N - 1); i++) {
			int U;
			LL C;
			cin >> U >> C;
			Edge[i].push_back(make_pair(U, C));
			Edge[U].push_back(make_pair(i, C));
		}
		for (int i = 0; i < M; i++) {
			Init2();
			int U, V;
			LL W;
			cin >> U >> V >> W;
			Edge[U].push_back(make_pair(V, W));
			Edge[V].push_back(make_pair(U, W));
			Settings();
		}
		Find_Answer();
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}