Cost(u,v)는 u와 v사이의 경로가 존재하지 않을 때 까지
그래프 상의 최소가중치 간선들을 지우고 그 값들의 합이다.
모든 u<v들에 대해 Cost(u,v)들의 합을 구하는 문제이다.
최소가중치 간선을 대신해 최대가중치 간선에 대해 생각해보자.
어떠한 정점 u,v상에 경로가 존재하지 않는다면 u와 v를 잇는 가장 큰 가중치 간선 보다
작거나 같은 간선들의 합이 pu = u에 속해있는 disjoint set,
pv = v에 속해있는 disjoint set 일 때 Cost(pu, pv)가 될 것이다.
즉, 위에서 초록색 간선으로 u,v상에 경로가 존재하지 않고 초록색 간선으로 연결하려 할 때
pu와 pv의 모든 쌍들의 Cost(pu,pv)를 구할 수 있다.
#include <cstdio>
#include <iostream>
#include <string>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <iomanip>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define mt(a,b,c) mp(a,mp(b,c))
#define mf(a,b,c,d) mp(mp(a,b),mp(c,d))
#define PI 3.14159265358979323846264
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define mod (ll)(1e9)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dy[] = { 0, 0, 1, -1 }; //동, 서, 남, 북
int dx[] = { 1, -1, 0, 0 };
const int MAXN = 100000 + 5;
int N, M;
vector<pair<int, pair<int, int>>> edge;
int par[MAXN], sze[MAXN];
ll sum;
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
}
void merge(int u, int v) {
if (sze[u] < sze[v]) swap(u, v);
par[v] = u;
sze[u] += sze[v];
sze[v] = 1;
}
int main() {
scanf("%d%d", &N, &M);
for (int n = 1; n <= N; n++) par[n] = n, sze[n] = 1;
for (int m = 0; m < M; m++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
edge.push_back({ d,{u,v} });
sum += d;
}
ll ans = 0;
sort(edge.begin(), edge.end());
for (int m = M - 1; m >= 0; m--) {
int u = edge[m].second.first, v = edge[m].second.second;
int tcost = edge[m].first;
int fu = find(u), fv = find(v);
if (fu != fv) {
ans += ((((ll)sze[fu] * sze[fv]) % mod) *sum) % mod;
ans %= mod;
merge(fu, fv);
}
sum -= tcost;
}
printf("%lld\n", ans);
return 0;
}
| cs |
