BOJ 19852 공정한 회의

문제 링크 입니다.

문제 요약

주어진 무방향 가중치 그래프를 다음의 조건을 만족하도록 간선을 추가해 완전 그래프로 만들어야 합니다.

• 임의의 세 정점 $a$, $b$, $c$에 대해, 세 정점을 잇는 세 간선 중 가중치가 최소인 것이 유일하게 존재해선 안 됩니다.

만들 수 있는 그래프의 최소 가중치 합을 구하세요.

관찰

두 간선 $ab$, $ac$의 가중치를 알고 있다고 합시다. 그러면 주어진 조건을 만족시키기 위해서는 간선 $bc$의 가중치가 $ab$와 $ac$의 가중치 중 더 작은 것과 같아야 함을 알 수 있습니다.

이는 가중치가 가장 큰 두 간선을 찾으면 나머지 한 간선도 자동으로 그릴 수 있음을 의미합니다. 따라서 가중치가 큰 간선부터 추가하면서 그래프를 구성해 낼 수 있음을 알 수 있습니다.

풀이

가중치가 큰 간선들부터 순서대로 그래프에 추가합니다. 이때 기존의 두 연결 요소가 하나로 합쳐지는 이벤트들이 발생할 거에요.

두 연결 요소가 각각 완전 그래프인 상태라고 생각해 봅시다. (처음에는 모든 정점이 크기가 1인 완전 그래프입니다!) 가중치가 큰 간선부터 추가했으므로 두 연결 요소를 이루는 모든 간선은 이번에 추가한 간선보다 가중치가 크거나 같습니다.

두 완전 그래프 $A$, $B$의 두 정점 $a$, $b$ 사이에 가중치가 $w$인 간선을 하나 추가했을 때 조건에 따라 가중치가 결정되는 간선을 찾아 봅시다. 먼저 $a$와 $A$의 다른 모든 정점 사이에 이미 간선이 있으므로 $b$와 $A$의 모든 정점을 잇는 간선들이 추가됩니다. 그러면 $A$에서 $a$를 포함한 정점 두 개, $B$에서 $b$를 골랐을 때 세 정점을 잇는 세 간선 중 두 개 이상이 모두 결정된 상태가 됩니다. 따라서 나머지 하나도 자동으로 그려지고, 합쳐진 연결 요소는 여전히 완전 그래프가 됩니다. 또한 새로 추가된 간선의 가중치가 최소이고 새로 그려진 모든 삼각형에 포함되므로, 두 연결 요소 사이에 $a$ 개의 가중치 $w$인 간선이 추가되게 됩니다.

그래프 구성이 불가능한 경우를 판정해야 합니다. 이는 간선을 추가하기 전에 이미 해당 간선의 양 끝 정점이 자신보다 가중치가 큰 간선들에 의해 같은 연결 요소가 되었는 지로 판정할 수 있습니다.

가중치가 동일한 간선이 여러 개 추가되는 경우에 주의하여 Union-Find 등으로 적절히 구현하면 총 시간 복잡도 ${\cal O}(N \lg N)$ 정도에 문제를 해결할 수 있습니다.

코드

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

ll ans;
ll par[303030];
map<ll, vector<pii>> E;

int f(int x){
	return par[x] < 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y); if(x == y) return;
	par[x] += par[y]; par[y] = x;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	memset(par, -1, sizeof(par));
	ll n, m; cin >> n >> m;
	ans = n*(n-1)/2;
	while(m--){
		int a, b, w; cin >> a >> b >> w; w--;
		E[-w].push_back({a,b});
	}
	for(auto& [w, e] : E){
		for(auto& [a, b] : e) if(f(a) == f(b)) return !(cout << -1);
		for(auto& [a, b] : e) if(f(a) != f(b)){
			ans -= par[f(a)]*par[f(b)]*w;
			u(a, b);
		}
	}
	cout << ans;
}