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;
}