문제 출처

1. 문제설명

  • 경로에 대한 그래프가 주어진다.
  • 그래프는 오르막길 또는 내리막길로 이루어져 있다.
    • 오르막길은 1, 내리막길은 0의 가중치

  • 최악의 경로와 최선의 경로를 구한 뒤 두 경로의 가중치 차이 값을 구하면 된다

  • 문제 분류
    • Graph, MST, Kruscal


2. 알고리즘 설계

  • MST 문제로 크루스칼 알고리즘을 사용했다.
  • 오르막길은 0, 내리막길은 1로 주어지므로, ! 연산자를 사용해 입력을 반전시켜 주었다.
  • 경로를 tuple<int,int,int>에 모두 담아 w가 작은 순, 큰 순으로 정렬을 해주고,
  • 정렬할 때마다 union-find를 수행해서 w 값을 더해주면 된다.
  • 작은 순으로 정렬된 건 최선의 경로이고, 그 반대는 최악의 경로이다.
  • w의 합의 제곱의 차가 정답값이 된다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
using ti3 = tuple<int,int,int>;

int u, v, w, n, m, P[1'002];
vector<ti3> adj;

int Find(int x) { 
	return P[x] = (x == P[x] ? x : Find(P[x]));
}
bool Union(int x, int y) {
	if(x == y) return false;
	P[x] = y;
	return true;
}

int solve() {
	int cnt = 0, sum = 0;

	for(int i=0; i<=n; i++) P[i] = i;

	for(auto [w, u, v] : adj) {
		if(Union(Find(u), Find(v))) {
			sum += w;
			if(++cnt == n) break;
		}
	}

	return sum;
}

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

	cin >> n >> m;
	for(int i=0; i<m+1; i++) {
		cin >> u >> v >> w;
		adj.push_back({!w, u, v});
	}

	sort(adj.begin(), adj.end());
	int mn = solve();

	sort(adj.rbegin(), adj.rend());
	int mx = solve();

	cout << mx*mx - mn*mn;

	return 0;
}