[BOJ] 10264 Particle Swapping

문제 링크: https://www.acmicpc.net/problem/10264

문제 요약

 평면 그래프에서 다음과 같은 쿼리를 처리해야 한다. 어떤 두 정점이 주어질 때, 각 정점에서 반대 정점으로 이동하는 개체 2개가 있다.  이동 중 개체 사이 거리의 최솟값이 가장 최대가 되도록 배치했을 때 거리의 최솟값을 구한다. 단, 경로에서는 간선은 따지지 않고 오직 정점만을 따진다.

문제 풀이

그래프를 적절히 바꿔서 모델링해보자. 정점 A에서부터 출발하는 개체와 정점 B에서 출발하는 개체의 위치를 순서쌍으로 표현해볼 수 있다. 만약 그렇다면 이동 중 개체 사이 거리의 최솟값은, 순서쌍을 정점으로 두고 순서쌍 사이의 상태 전이가 가능한 경우를 적당히 간선으로 이어줬을 때 (A,B)에서 (B,A)로 이동하면서 찾아줄 수 있다. 이렇게 된다면 각 정점마다 두 개체의 거리라는 가중치를 가지게 된다.

이렇게 그래프를 모델링한다면 자연스럽게 쿼리 하나를 파라메트릭 서치로, k 이상의 거리를 유지하면서 (A,B)에서 (B,A)로 이동하는 경로가 있는지에 관한 결정 문제를 해결함으로서 계산하려는 생각에까지 미치게 된다. 이를 위해서는 가중치가 k 이상인 정점만을 방문해야 하는데, 복잡하게 생각할 필요 없이 두 정점 p와 q를 잇는 상태 전이가 존재한다면 가중치가 min(p,q)인 간선을 이어줌으로서 정점에 대한 문제를 간선에 대한 문제로 바꿔줄 수 있다. 결론적으로, 문제는 그래프가 주어졌을 때 다음과 같은 쿼리를 처리하는 것으로 바뀐다.

• 정점 쌍이 Q개 주어질 때, 각 정점 쌍에 대해 가중치가 K 이상인 간선만을 사용해서 두 정점을 이을 수 있게 하는 최소 K를 구하여라.

이는 1396번 크루스칼의 공과 같은 문제다. 풀이는 다음을 참고하자.

2020/01/24 - [Problem Solving/문제풀이] - [BOJ] 1396 크루스칼의 공

코드

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> edge;

int n, m;
pii pt[505];
int val[300000];
int depth[600000], par[600000][20], timed[600000], inter[600000], top = 1;
vector<int> child[600000];

int dist(pii fp, pii sp) {
	return (fp.x - sp.x)*(fp.x - sp.x) + (fp.y - sp.y) * (fp.y - sp.y);
}

vector<int> pa, idx;
void init(int _n) {
	pa.assign(_n + 1, 0); idx.assign(_n + 1, 0);
	for (int i = 1; i <= _n; i++) pa[i] = idx[i] = i;
	for (int i = 1; i <= _n; i++) par[i][0] = top++;
}
int fi(int t) {
	if (t == pa[t]) return t;
	else return pa[t] = fi(pa[t]);
}
void un(int a, int b, int tx) {
	a = fi(a); b = fi(b);
	if (a == b) return;

	pa[a] = b;
	par[top][0] = par[idx[a]][0] = par[idx[b]][0] = top;
	inter[idx[a]] = inter[idx[b]] = 1;
	timed[top] = tx;
	child[top].push_back(idx[a]); child[top].push_back(idx[b]);
	idx[b] = top;
	top++;
}

void dfs(int h, int dp) {
	depth[h] = dp;
	for (int th : child[h])
		dfs(th, dp + 1);
}

void process() {

	for (int i = 1; i < top; i++)
		if (!inter[i]) dfs(i, 1);

	for (int i = 1; i <= 19; i++)
		for (int j = 1; j < top; j++)
			par[j][i] = par[par[j][i - 1]][i - 1];
}

int lca(int a, int b) {
	if (depth[a] > depth[b]) swap(a, b);
	int sub = depth[b] - depth[a];
	int k = 0;
	while (sub) {
		if (sub & 1) b = par[b][k];
		sub = sub >> 1; k++;
	}
	if (a == b) return a;
	for (int i = 19; i >= 0; i--) {
		if (par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> pt[i].first >> pt[i].second;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			val[i*n + j] = dist(pt[i], pt[j]);

	cin >> m;
	vector<edge> e;
	for (int i = 0; i < m; i++) {
		int p, q; cin >> p >> q;
		for (int j = 1; j <= n; j++) {
			e.emplace_back(min(val[p*n + j], val[q*n + j]), p*n + j, q*n + j);
			e.emplace_back(min(val[j*n + p], val[j*n + q]), j*n + p, j*n + q);
		}
	}

	init(n*n+n);
	sort(e.begin(), e.end(), greater<edge>());
	for (int i = 0; i < e.size(); i++) {
		int v, st, en;
		tie(v, st, en) = e[i];
		un(st, en, i);
	}
	process();
	cout << fixed;
	cout.precision(10);
	int q;  cin >> q;
	while (q--) {
		int st, en;
		cin >> st >> en;
		int l = timed[lca(st*n + en, en*n + st)];
		cout << sqrt(get<0>(e[l])) << '\n';
	}
	return 0;
}