[백준 13418] 학교 탐방하기 (C++)

이 문제는 비용이 최소인 경로와 비용이 최대인 경로를 구해, 둘의 차를 출력하는 문제이다. 따라서, MST를 2번 구하는 것과 일맥상통한다. 크루스칼 알고리즘으로 구할 것인데, 한 번은 간선을 오름차순으로 정렬하고 다른 한 번은 내림차순으로 정렬하여 간선들을 $N$개 선택하도록 하면 된다. 정점이 $0$ ~ $N$까지 $N + 1$개가 있기 때문이다.

이를 바탕으로 구현해보면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
vector<tuple<int, int, int>> edge;
vector<int> p;

int find(int x) {
	if (p[x] < 0) return x;
	return p[x] = find(p[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	p[y] = x;
}

ll kruskal(int dir) {
	if (dir) reverse(edge.begin(), edge.end());
	ll cnt = 0, cost = 0;
	p = vector<int>(1001, -1);
	for (int i = 0, a, b, c; i < m + 1; i++) {
		tie(c, a, b) = edge[i];
		if (find(a) == find(b)) continue;
		merge(a, b);
		cost += c;
		cnt++;
		if (cnt == n) break;
	}
	return cost * cost;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0, a, b, c; i < m + 1; i++) {
		cin >> a >> b >> c;
		edge.push_back({1 - c, a, b});
	}
	sort(edge.begin(), edge.end());
	cout << abs(kruskal(0) - kruskal(1));
}