📝 문제 정보#
🧐 관찰 및 접근#
- 간선에 가중치가 주어진 무향 그래프가 있다.
- 모든 간선의 가중치는 서로 다르다.
- $u$와 $v$사이의 최소 가중치 간선을 그래프에서 계속 제거해나가면서 $\text{Cost}(u, v)$를 구한다.
- $u, v$사이의 경로는 최대 가중치 간선만 남아있다.
- MST를 최댓값으로 하면 된다!
- 최댓값부터 MST를 진행하면서, 간선이 연결될때 양쪽 그룹의 크기의 곱만큼의 $\text{Cost}$ 관계를 계산하면서 구현할 수 있어보인다.
- $u, v$사이의 경로는 최대 가중치 간선만 남아있다.
💻 풀이#
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
vector<array<int, 3>> edges;
mint sum = 0;
rep(i, 0, M){
int u, v, w; cin >> u >> v >> w;
edges.push_back({w, u, v});
sum += w;
}
sort(all(edges), greater<array<int, 3>>());
UnionFind UF(N+1);
mint ans = 0;
for(auto [w, u, v]: edges){
if(UF.find(u) != UF.find(v)){
ans += sum * UF.cnt[UF.find(u)] * UF.cnt[UF.find(v)];
UF.merge(u, v);
}
sum -= w;
}
cout << ans << '\n';
}