Sum of Maximum Weights
問題
D – Sum of Maximum Weights
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…
記録
- 2022/7/14 なんとかAC。
解法
- UnionFind
コード例
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using P = pair<int, int>; #define rep(i, n) for(int i = 0; i < (n); ++i) // using mint = modint998244353; // using mint = modint1000000007; // const int mod = 1000000007; // const ll INF = 1LL << 62; // const int INF = 1001001001; int main() { int N; cin >> N; vector<pair<ll, P>> edges; rep(i, N - 1){ int u, v; ll w; cin >> u >> v >> w; --u; --v; edges.push_back(make_pair(w, make_pair(u,v))); } sort(edges.begin(), edges.end()); dsu uf(N); ll ans = 0; rep(i, N - 1) { pair<ll, P> e = edges[i]; ll w = e.first; P e2 = e.second; ans += w * (ll) uf.size(e2.first) * (ll) uf.size(e2.second); uf.merge(e2.first, e2.second); } cout << ans << endl; return 0; }