백준 - 도시 분할 계획 (1647) [C++]

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

 

최소 스패닝 트리는 모든 정점을 연결한 최소의 가중치의 부분 그래프를 의미한다.

문제에서는 마을을 두 개의 분리된 마을로 분할해야 하고, 마을에는 집이 하나 이상 있어야 한다는 요구사항이 있다.

 

최소 스패닝 트리가 모든 정점을 연결한 최소 가중치의 부분 그래프라면, 크루스칼 알고리즘을 통해 MST를 만들 때 마지막으로 merge된 간선을 빼준다면 두 개의 부분 트리가 만들어 질 것이라고 예상하고 문제를 풀었고 정답을 맞출 수 있었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX 100000

struct Edge {
	int a;
	int b;
	int cost;
};

vector<Edge> edges;
int N, M;
int parent[MAX + 1];

bool compare(Edge &A, Edge &B) {
	return A.cost < B.cost;
}

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

int find(int x) {
	if (parent[x] != x) {
		return parent[x] = find(parent[x]);
	}
	return x;
}

bool merge(int a, int b) {
	a = find(a);
	b = find(b);

	if (a == b) {
		return false;
	}

	if (a < b) {
		parent[b] = a;
	} else {
		parent[a] = b;
	}
	return true;
}

void input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		edges.push_back({ A,B,C });
	}
}

int solve() {
	int result = 0;
	int last = -1;

	init();
	sort(edges.begin(), edges.end(), compare);
	for (Edge &edge : edges) {
		int a = edge.a;
		int b = edge.b;
		int cost = edge.cost;

		if (merge(a, b)) {
			result += cost;
			last = cost;
		}
	}

	return result - last;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	input();
	cout << solve() << '\n';

	return 0;
}