JAG 2012春コンテスト E - Minimum Spanning Tree

問題

n頂点m辺からなる重みつき無向グラフが与えられる。
これらのうち、i番目の辺(s[i], t[i])を使わないで作った最小全域木の重みを
全てのiについて求めよ。

制約条件

n≦100000
m≦200000
重みは0以上10^6以下の整数

方針

まずは制限のない最小全域木を作る。
作れない場合は-1を返す。

求める最小全域木は、制限のない最小全域木について
i番目の辺が含まれてないなら、制限の最小全域木と同じ、
含まれるなら、その辺を削除して、分かれた二成分のうち、それぞれをつなぐ、
最も重みの小さい辺を、二成分に加えたもの。

これを効率的に求めたい。
頂点vを根とする部分木について、そこから部分木の外へ出るエッジの集合をE[v]とする。
これのうち重み最小のものの重みがわかれば、vとvの親をつなぐエッジを切断したときに、最小全域木を作り直すコストがわかる。

これを、根から順に統合していけば、全てのクエリに対して高速に最小の重みが求まる。
普通に統合するとO(nm)がかかりそうだが、
小さいほうの要素を大きいほうの要素に入れるとやれば、O(mlogm)回の統合だけですむ。

ソースコード

const int MX = 200000;
int n, m, a[MX], b[MX], w[MX];
vector<vector<pi> > e;

vi ord;
int parent[MX], pid[MX];

int euler[MX], sz, s[MX], t[MX];
int of[MX], use[MX];
ll cost, ans[MX];
set<pi> we[MX];

int p[MX];
int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}

void rec(int c, int p){
	vi C, P, I;
	int i;
	C.pb(c); P.pb(p);
	ONE:
	c = C.back();
	p = P.back();
	
	ord.pb(c);
	euler[sz] = c;
	s[c] = sz++;
	
	for(i = 0; i < e[c].size(); i++) if(e[c][i].first != p){
		C.pb(e[c][i].first); P.pb(c); I.pb(i);
		
		pid[e[c][i].first] = e[c][i].second;
		parent[e[c][i].first] = c;
		
		goto ONE;
		TWO:
		c = C.back(); p = P.back(); i = I.back(); I.pop_back();
	}
	euler[sz] = c;
	t[c] = sz++;
	C.pop_back(); P.pop_back();
	if(C.size()) goto TWO;
}
void rec2(int c, int p, int eid){
	if(c == p) eid = -1;
	
	priority_queue<pi> q;
	rep(i, e[c].size()) if(e[c][i].first != p){
		q.push(mp(-we[of[e[c][i].first]].size(), e[c][i].first));
	}
	q.push(mp(we[of[c]].size(), c));
	while(q.size() > 1){
		int a = q.top().second; q.pop();
		int b = q.top().second; q.pop();
		
		each(i, we[of[a]]) we[of[b]].insert(*i);
		q.push(mp(-we[of[b]].size(), b));
	}
	of[c] = of[q.top().second];
	
	while(we[of[c]].size() && s[c] <= we[of[c]].begin()->second && we[of[c]].begin()->second <= t[c])
	we[of[c]].erase(we[of[c]].begin());
	
	if(eid >= 0){
		ans[eid] = we[of[c]].empty() ? -1 : cost - w[eid] + we[of[c]].begin()->first;
	}
}

int main(){
	scanf("%d%d", &n, &m);
	vector<pi> es;
	rep(i, m){
		scanf("%d%d%d", a + i, b + i, w + i);
		a[i]--; b[i]--;
		es.pb(mp(w[i], i));
	}
	
	rep(i, n) p[i] = of[i] = i;
	e.resize(n);
	sort(all(es));
	int cmp = n;
	
	rep(i, m){
		int id = es[i].second, x = a[id], y = b[id];
		if(root(x) == root(y)) continue;
		e[x].pb(mp(y, id));
		e[y].pb(mp(x, id));
		
		cost += es[i].first;
		use[id] = 1;
		p[root(x)] = root(y);
		cmp--;
	}
	if(cmp != 1){
		rep(i, m) puts("-1");
		return 0;
	}
	
	rec(0, 0);
	rep(i, m) if(!use[i]){
		we[a[i]].insert(mp(w[i], s[b[i]]));
		we[b[i]].insert(mp(w[i], s[a[i]]));
	}
	
	rep(i, m) ans[i] = cost;
	for(int i = ord.size() - 1; i >= 0; i--){
		rec2(ord[i], parent[ord[i]], pid[ord[i]]);
	}
	rep(i, m) printf("%lld\n", ans[i]);
	
	return 0;
}