BOJ 34901 자재 옮기기

문제 링크입니다.

문제 요약

$W_{i \to j} = dist(i, j) + c_j$인 방향 완전 그래프의 각 정점에 대해, 해당 정점으로 들어오는 방향의 MST의 가중치 합을 구하세요.

$dist(i, j)$는 $i$번 정점과 $j$번 정점 사이의 맨해튼 거리입니다.

풀이

$dist$가 뭔지는 답을 실제로 계산할 때만 필요해서 그냥 $dist$로 인지하는게 편합니다. 또 $i$번 정점의 차수를 $deg_i$로 표기하겠습니다.

$W_{ij} = dist(i, j)+c_i+c_j$인 무방향 완전 그래프의 MST를 고려합니다. 이 MST는 $\sum dist + \sum deg_i \cdot c_i$의 값을 최소화합니다. 실제로 우리에게 필요한 값은 각 정점 $x$에 대해서 $\sum dist + \sum\limits_{i \neq x} (deg_i - 1) \cdot c_i + deg_x \cdot c_x$입니다. 이는 위의 값에서 $\sum c_i - c_x$를 뺀 값과 같으며, 빼는 값이 상수기 때문에 위의 MST의 간선들이 실제로 최적해를 만드는 간선들임을 알 수 있습니다.

MST를 ${\cal O}(N^2 \lg N)$에 구축해주면 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

priority_queue<pair<ll, int>> pq;
ll x[2020], y[2020], c[2020], ans; bool vis[2020];
ll W(int i, int j){
	return abs(x[i]-x[j])+abs(y[i]-y[j])+c[i]+c[j];
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; for(int i = 1; i <= n; i++) cin >> x[i] >> y[i] >> c[i], ans -= c[i];
	vis[1] = 1; for(int i = 2; i <= n; i++)  pq.push({-W(1, i), i});
	while(pq.size()){
		auto [w, now] = pq.top(); pq.pop(); if(vis[now]) continue; vis[now] = 1; ans -= w;
		for(int i = 1; i <= n; i++) if(!vis[i]) pq.push({-W(now, i), i});
	}
	for(int i = 1; i <= n; i++) cout << ans+c[i] << ' ';
}