UTPC 2013 : F - 魔法の糸

これは自力ではTLEが回避できず。
http://utpc2013.contest.atcoder.jp/tasks/utpc2013_06

問題

N点・M辺の無向グラフが与えられる。
初期状態で、各点は個別のグループとなっている。

ここでQ個のクエリが与えられる。
各クエリでは、p番の点を含むグループとq番の点を含むグループを併合する。
この時、併合後のグループに含まれる点を連結する最小木の長さを答えよ。

解法

1度併合後の最小木構築で使われなかった辺は以後使われない。

よって、各クエリにおいて以下の辺で最小木を構築すればよい。

1. p番のグループを構成する最小木に含まれる辺
2. q番のグループを構成する最小木に含まれる辺
3. p番のグループとq番のグループを結ぶ辺

点が2000個あるので、3番に含まれる辺は最大min(1000^2,M)本程度ある。
しかしいったん最小木を作れば3つのうち(N-1)辺以下しか残らないので、毎回のクエリでそんなたくさんの辺を処理する必要はない。

class UF {
	public:
	static const int ufmax=2002;
	int ufpar[ufmax],ufrank[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

int N,M,Q,num[2002];
int mat[2002][2002];
vector<pair<int,pair<int,int> > > E[2001];
vector<pair<int,pair<int,int> > > TE;
UF uf;

void solve() {
	int f,i,j,k,l,x,y,z;
	
	cin>>N>>M;
	FOR(i,N) num[i]=1;
	FOR(i,M) {
		cin>>x>>y>>l;
		mat[x][y]=mat[y][x]=l;
	}
	TE.reserve(200000);
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		UF uf2;
		int x2=uf[x],y2=uf[y];
		
		TE.clear();
		
		ITR(it,E[x2]) TE.push_back(*it);
		ITR(it,E[y2]) TE.push_back(*it);
		E[x2].clear();
		E[y2].clear();
		
		vector<int> g1,g2;
		FOR(i,N) if(uf[i]==x2) g1.push_back(i);
		FOR(i,N) if(uf[i]==y2) g2.push_back(i);
		ITR(it,g1) ITR(it2,g2) if(mat[*it][*it2]) TE.push_back(make_pair(mat[*it][*it2],make_pair(*it,*it2)));
		sort(TE.begin(),TE.end());
		
		uf.unite(x,y);
		z=uf.find(x);
		num[z]=num[x2]+num[y2];
		
		ll tot=0;
		int nv=num[z];
		
		
		E[z].clear();
		ITR(it,TE) {
			int fi=it->second.first;
			int se=it->second.second;
			if(uf2[fi]==uf2[se]) continue;
			uf2.unite(fi,se);
			tot += it->first;
			nv--;
			E[z].push_back(*it);
		}
		
		if(nv>1) tot=-1;
		if(tot==-1) cout << "IMPOSSIBLE" << endl;
		else cout << tot << endl;
	}
}

まとめ

うまく不使用な辺を落とせなかったけど、落とすのではなく毎回グループ間を結ぶ辺だけ足していけばよかったのね。