[BOJ | 백준] 2463번: 비용

by Kimcoding on 2020-03-31 04:48

in BOJ

문제 설명

BOJ 2463

A < B인 모든 두 정점에 대한 Cost(A,B)의 합을 구하는 문제입니다.

풀이

유니온 파인드 문제입니다.

크루스칼을 구현하듯이 문제를 풀어주시면 됩니다.

A, B의 경로가 없을 때까지 최소 가중치 간선부터 제거하게 되는데

이를 제거하면서 경로 유무를 판별하게 되면 시간이 오래 걸립니다.

그러므로 반대로 간선이 없는 상태에서 최대 가중치 간선을 연결해 가며 이 간선이 추가되었을 때 (A,B) 경로가 있는 정점들을 구하겠습니다.

간선들을 가중치 기준으로 정렬을 하여 최대 가중치부터 봅니다.
가중치를 추가할 때 유니온파인드로 간선의 두 정점이 같은 집합인지 확인합니다.
같은 집합이 아니라면 각 집합의 정점의 개수를 곱하여 경우의 수를 구하고 현재 Cost값과 곱하고 집합을 합쳐줍니다.
같은 집합이 맞다면 넘어갑니다.
1~4과정을 반복하면 됩니다.

현재 Cost값은 간선의 총 합 중에 간선을 추가하기 전의 합입니다. 간선을 추가했을 때 합에서 간선의 가중치를 빼면 됩니다.

어렵지 않았지만 역순으로 생각하는 게 흥미로운 문제였습니다.

비슷한 문제들을 풀어보고 싶네요!

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define RFOR(i,a,b) for(int i=a;i>=b;i--)
#define mod (int)1e9
using namespace std;

struct Edge {
	int a, b, w;
	bool operator< (const Edge& t)const {
		return w < t.w;
	}
};

struct UF {
	int* v, * sz;
	UF(int n) {
		v = new int[n + 1];
		sz = new int[n + 1];
		FOR(i, 1, n) v[i] = i, sz[i] = 1;
	}
	int find(int x) {
		return v[x] == x ? x : x = find(v[x]);
	}
	void merge(int x, int y) {
		x = find(x), y = find(y);
		if (sz[x] > sz[y]) swap(x, y);
		v[x] = y, sz[y] += sz[x];
	}
	~UF() {
		delete[] v, delete[] sz;
	}
};

int main() {
	FIO;
	int n, m; cin >> n >> m;
	Edge* e = new Edge[m];
	int sum = 0, ans = 0;
	FOR(i, 0, m - 1) {
		int x, y, w; cin >> x >> y >> w;
		e[i] = Edge{ x,y,w };
		sum = (sum + w) % mod;
	}
	sort(e, e + m);
	UF uf(n);
	RFOR(i, m - 1, 0) {
		int x = uf.find(e[i].a);
		int y = uf.find(e[i].b);
		if (x != y) {
			ans = (ans + 1ll * sum * uf.sz[x] * uf.sz[y]) % mod;
			uf.merge(x, y);
		}
		sum = (sum - e[i].w + mod) % mod;
	}
	cout << ans << '\n';
	return 0;
}