UTPC2013 F 魔法の糸

グラフ理論 データ構造

問題

日本語なので本文参照（http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06）


n頂点からなる無向グラフが与えられる。
最初全ての頂点は自分自身だけかならるグループで、クエリによりグループ同士をマージしていく。


グループA, Bをマージした後、新しくできたグループをCとする。
C内部の頂点同士を接続する辺だけを使ってCを連結にするコストを求めよ、というクエリが沢山くるので答えよ。


一度マージしたグループは分かれることはない。
マージのたびに連結にかかるコストはリセットして求める。

制約条件

n≦2000
m≦200000
クエリ＜n

方針

グループの中の辺は、グループで最小全域木を使うのに使う辺以外は捨ててしまってよい。
（余分な辺を使って後々別のグループとマージしたときに全域木を作るのに有利になるかというと、ならないので）


グループA, Bをマージするときは、
Aから出てBに入るorBから出てAに入る辺だけを見ればいい。


外に出てる辺が少ないグループを多いグループに統合すれば、
枝のマージ回数があまり多くならなくて済む。
（最悪計算量がいくつなのかよくわかってない）


で、マージした後、全域木を作って、
使わなかった辺は全部捨てる、というのを繰り返せばいい。

ソースコード

#define F first
#define S second
 
int n, m, p[2000];
map<pi, int> inner[2000], outer[2000];
 
int root(int x){
	if(p[x] < 0) return x;
	return p[x] = root(p[x]);
}
 
int p2[2000];
int root2(int x){
	if(p2[x] == x) return x;
	return p2[x] = root2(p2[x]);
}
 
int calc(const vi & v, map<pi, int> &g){
	vector<pair<int, pi> > es;
	vector<pi> del;
	
	each(i, g) es.pb(mp(i->S, i->F));
	sort(all(es));
	
	int res = 0, cnt = 0;
	rep(i, 2000) p2[i] = i;
	
	rep(i, es.size()){
		int a = es[i].S.F, b = es[i].S.S;
		//cerr<<"e:: "<<a<<" "<<b<<endl;
		a = root2(a); b = root2(b);
		
		if(a == b){
			del.pb(es[i].S);
			continue;
		}
		p2[a] = b;
		cnt++;
		res += es[i].F;
	}
	
	rep(i, del.size()) g.erase(del[i]);
	
	return cnt == v.size() - 1 ? res : -1;
}
int main(){
	cin >> n >> m;
	rep(i, n) p[i] = -1;
	
	rep(i, m){
		int a, b, c;
		cin >> a >> b >> c;
		outer[a][mp(a, b)] = c;
		outer[b][mp(b, a)] = c;
	}
	int qs; cin >> qs;
	while(qs--){
		int a, b;
		cin >> a >> b;
		
		a = root(a); b = root(b);
		
		if(outer[a].size() > outer[b].size()) swap(a, b);
		//cerr<<"a: "<<a<<" b: "<<b<<endl;
		
		each(i, outer[a]){
			if(root(i->F.S) == b){
				
				int x = i->F.F, y = i->F.S;
				if(x > y) swap(x, y);
				//cerr<<"x: "<<x<<" y: "<<y<<endl;
				inner[b][mp(x, y)] = i->S;
			}
			else{
				outer[b][i->F] = i->S;
			}
		}
		each(i, inner[a]) inner[b][i->F] = i->S;
		p[a] = b;
		
		vi v;
		rep(i, n) if(root(i) == b) v.pb(i);
		int dist = calc(v, inner[b]);
		
		if(dist < 0) cout << "IMPOSSIBLE" << endl;
		else cout << dist << endl;
	}
	
	return 0;
}