ARC 029 C - 高橋君と国家
問題
n頂点m辺のグラフの全ての頂点を「直接良い状態にするか、良い道路を辿って良い頂点へ辿りつける」ようにしたい。
i番目の頂点が良い状態であるようにするにはci円
j番目の道路はaj, bjを結んでいて双方向に通行可能であり、良い道路にするにはcj円かかる。
必要なコストの最小値を求めよ。
制約条件
n≦10^5
m≦2 * 10^5
方針
クラスカルっぽくunion-findしていく。
辺と辺をつなぐクエリの他に、そのunionを良い状態にするクエリも入れる。
既に良い状態になっているunion同士をつなぐクエリ、
既に良い状態になっているunionを良い状態にするクエリは無視。
ソースコード
const int MX = 200000; int n, m; vector<pair<int, pi> > v; int p[MX], ok[MX]; int root(int x){ if(x == p[x]) return x; return p[x] = root(p[x]); } void merge(int a, int b){ a = root(a); b = root(b); if(a != b) p[b] = a; } int main(){ scanf("%d%d", &n, &m); rep(i, n){ int c; scanf("%d", &c); v.pb(mp(c, mp(i, i))); } rep(i, m){ int a, b, c; scanf("%d%d%d", &a, &b, &c); v.pb(mp(c, mp(a - 1, b - 1))); } sort(all(v)); rep(i, n) p[i] = i; ll ans = 0; int cmp = n; rep(i, v.size()){ int a = v[i].second.first, b = v[i].second.second; int c = v[i].first; if(a == b){ if(ok[root(a)]) continue; ok[root(a)] = 1; } else{ a = root(a); b = root(b); if(ok[a] && ok[b] || a == b) continue; if(ok[a] || ok[b]) ok[a] = ok[b] = 1; merge(a, b); } ans += c; if(--cmp == 0) break; } cout << ans << endl; return 0; }