[ABC218] E - Destruction
[Q] https://atcoder.jp/contests/abc218/tasks/abc218_e
UnionFind。
1, 価値が低いものからuniteする。
2. 連結確認ができたら、以降は得点の加算。
=> 2頂点がすでにissameなら加算、かも。(2WA)
※負の辺は切らなくてもいいからマイナスしなくてもいい。
似たような問題が最近のABCであったと思う。（さがしちゅう）
これだ
D - Sum of Maximum Weights
https://atcoder.jp/contests/abc214/tasks/abc214_d
まったく同じ解法。得点の低いものからuniteしていく。
Q. 200010?
A. 辺の数がN(N-1)なので、160000くらいまで入りうる(2RE)
ll A[200010];
ll B[200010];
int main(){
ll N, M;
cin >> N >> M;
vector<pll> C(M);
rep(i, M){
ll a, b, c;
cin >> a >> b >> c;
--a, --b;
A[i] = a;
B[i] = b;
C[i] = {c, i};
}
sort(all(C)); // 価値でソート
UnionFind tree(N);
bool fin = false;
ll ans = 0;
rep(i, M){
ll id = C[i].second;
ll c = C[i].first;
if (fin){
ans += max(0LL, c);
continue;
}
ll a = A[id];
ll b = B[id];
if (tree.issame(a, b)){ // 連結しても要素が変わらないなら加算対象。
ans += max(0LL, c);
}
else tree.unite(a, b);
if (tree.size(0) == N) fin = true; // 連結したらfinフラグ
}
cout << ans << endl;
}