[BOJ | 백준] 14950번: 정복자

by Kimcoding on 2020-03-26 18:23

in BOJ

문제 설명

BOJ 14950

1번 도시에서 다른 도시들을 정복할 때 모든 도시들을 정복하는데 사용되는 최소 비용을 출력하는 문제입니다.

풀이

MST(최소 신장 트리)문제입니다.

한 도시가 정복될 때마다 t만큼 모든 도로의 비용이 증가합니다.

도시 하나를 정복하면 그 도시는 정복을 할 필요가 없으므로 도시들을 모두 정복할 때 횟수는 어떤 식으로 정복하던지 비용 증가의 합은 항상 같습니다.

그러므로 따로 계산하겠습니다.

도시를 정복하려면 현재 도시에서 다음 도시로 가는 경로의 비용이 소모됩니다.

모든 도시를 연결하는 간선을 최소 비용으로 만들고 그 비용만 계산하면 됩니다.

기본적인 MST를 구현하면 됩니다. 저는 크루스칼을 구현했습니다.

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
#define vi vector <int>
#define all(x) (x).begin(), (x).end()
#define ep emplace
#define eb emplace_back
using namespace std;

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

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

int main() {
	FIO;
	int n, m, k; cin >> n >> m >> k;
	vector <Edge> v;
	FOR(i, 0, m - 1) {
		int a, b, w; cin >> a >> b >> w;
		v.eb(Edge{ a,b,w });
	}
	sort(all(v));
	UF uf(n);
	int ans = 0;
	FOR(i, 0, m - 1) {
		int a = v[i].a, b = v[i].b;
		if (uf.find(a) == uf.find(b)) continue;
		uf.merge(a, b);
		ans += v[i].w;
	}
	FOR(i, 1, n - 2) ans += i * k;
	cout << ans << '\n';
	return 0;
}