백준 1396번 (병렬 이분 탐색/PBS), 크루스칼의 공

문제

BOJ 1396번

풀이

쿼리가 하나 있다고 가정하면 아래와 같이 풀 수 있습니다.

 

* mid보다 작거나 같은 간선들만 합쳐줍니다. (Union Find)

* (쿼리) 정점 u와 v의 루트 노드가 같으면, right를 mid로 두고 그렇지 않으면 left를 mid + 1로 만들어준 뒤 계속 이분 탐색을 돌립니다.

 

 - 가중치(고유값)이 mid 이하인 간선을 이용해 정점 u, v를 포함하는 MST를 구성할 수 있냐 는 결정 문제로 볼 수 있습니다.

 

위와 같은 이분 탐색을 사용하면 간선을 이분 탐색하는데 $ O(log M) $, mid보다 작거나 같은 간선을 합치는데(MST를 만드는데) 시간이 $ O(M logN) $ 이고, 쿼리가 총 $ Q $개 있으니 총 시간 복잡도는 $ O (QM log N log M) $ 입니다.

 

대충봐도 TLE가 날 것 같습니다.

 

 

UF를 초기화하고 MST를 만드는데 시간이 너무 오래 걸립니다.

같은 mid에 대해서는 MST를 여러번 초기화하고 만들 필요 없이 한번만 만들면 됩니다.

 

즉, 매 결정 문제를 풀 때마다 MST를 만들지 않고, 같은 mid에 대해서 한번에 처리해주면 더 빠르게 풀 수 있습니다.

 

 

관련글) MST를 구성하는 크루스칼 알고리즘 글

 

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

vector<pair<int, pair<int, int>>> nodes(1);
vector<pii> query(1), range(1);

int UF[100001], cnt[100001];
pii ans[100001];

int find(int a) {
	return a == UF[a] ? a : UF[a] = find(UF[a]);
}

void merge(int a, int b) {
	int x = find(a), y = find(b);
	if (x != y) UF[x] = y, cnt[y] += cnt[x], cnt[x] = 0;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);

	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c; cin >> a >> b >> c;
		nodes.emplace_back(c, pii{a, b});
	}

	sort(nodes.begin(), nodes.end());

	int q; cin >> q;
	for (int i = 1; i <= q; i++) {
		int u, v; cin >> u >> v;
		query.emplace_back(u, v);
		range.emplace_back(1, m + 1);
	}

	vector<vector<int>> mid(m + 1);
	while (1) {
		for (int i = 1; i <= m; i++) mid[i].clear();

		int flag = 0;
		for (int i = 1; i <= q; i++) {
			if (range[i].first != range[i].second) {
				flag = 1;
				mid[range[i].first + range[i].second >> 1].emplace_back(i);
			}
		}
		if (!flag) break;

		for (int i = 1; i <= n; i++) UF[i] = i, cnt[i] = 1;

		for (int i = 1; i <= m; i++) {
			merge(nodes[i].second.first, nodes[i].second.second);
			for (const auto &k : mid[i]) {
				if (find(query[k].first) == find(query[k].second)) {
					ans[k].first = nodes[i].first;
					ans[k].second = cnt[find(query[k].first)];

					range[k].second = i;
				} else {
					range[k].first = i + 1;
				}
			}
		}
	}

	for (int i = 1; i <= q; i++) {
		if (ans[i].second) cout << ans[i].first << " " << ans[i].second << "\n";
		else cout << "-1\n";
	}
}

 

* 감사합니다) justicehui.github.io/hard-algorithm/2020/02/24/pbs/

병렬 이분 탐색