[백준-1647] 도시 분할 계획

최소 스패닝 트리 문제이다.

일단 시간제한부터 보면 2초의 제한을 가지고 있다. 그 후 입력값의 범위를 보면 100000 개 이하의 노드와 1000000(백만개) 이하의 edge 가 있는 것을 볼 수 있다.

이 문제를 크루스칼을 통해 구하게 되면 nlog(n) 의 복잡도를 가지게 되어 널널하게 통과할 수 있다. (크루스칼 → 사실상 정렬알고리즘과 union-find 알고리즘의 복잡도와 비슷하다.)

여튼 크루스칼 알고리즘으로 최소 weight 를 가지는 edge 부터 차근차근 cycle 이 있는지 확인해가며 처리해주면 쉽게 풀리는 문제이다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;

int n, m;
int root[100001];
struct Node {
	int to, from, weight;
	Node(int a, int b, int c) : to(a), from(b), weight(c) {};
};

struct compare {
	bool operator()(Node a, Node b) {
		return a.weight > b.weight;
	}
};
int get_union(int a) {
	if (root[a] == a) return a;
	else {
		return get_union(root[a]);
	}
}

void set_union(int a, int b) {
	int ta = get_union(a);
	int tb = get_union(b);

	if (ta < tb) root[tb] = ta;
	else root[ta] = tb;
}
priority_queue<Node, vector<Node>, compare> pq;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	
	int ta, tb, tc;
	for (int i = 0; i < m; i++) {
		cin >> ta >> tb >> tc;
		Node tp(ta, tb, tc);
		pq.push(tp);
	}
	for (int i = 1; i <= n; i++) 
		root[i] = i;
	

	int _to, _from, _weight, res = 0;
	int _max = 0;
	while (!pq.empty()) {
		_to = pq.top().to;
		_from = pq.top().from;
		_weight = pq.top().weight;
		pq.pop();

		if (get_union(_to) == get_union(_from)) continue;
		else {
			set_union(_to, _from);
			res += _weight;
			_max = max(_max, _weight);
		}
	}
	cout << res - _max;
	return 0;
}

 

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

1647번: 도시 분할 계획