kmjp's blog

競技プログラミング参加記です

CODE FESTIVAL 2016 Qual B : C - Gr-idian MST

割とすんなり行けた。
http://code-festival-2016-qualb.contest.atcoder.jp/tasks/codefestival_2016_qualB_c

問題

(0,0)-(H,W)の矩形範囲内の格子点がある。
(i,j)-(i+1,j)をつなぐ辺を1つ張るとコストがP[i],(i,j)-(i,j+1)をつなぐ辺を1つ張るとコストがQ[i]かかるとする。
これらの点を結んで全域木を作るのに必要な辺を張る最小コストを求めよ。

解法

格子点は縦に(H+1)列、横に(W+1)列ならんでいる。

例えば(i,*)-(i+1,*)とある列に関し各行P[i]の辺を張る。
すると次縦方向の辺を張るとき、横に(W+1)列あったがi列と(i+1)列は既に連結なので、1列分辺の数を減らしてよい。

この考察を進めていく。
P[i],Q[j]をひっくるめてコスト順に昇順ソートして、コストの小さい順に使っていく。
縦・横それぞれの辺を張る際は、既に縦・横それぞれ何行/何列連結済みであと何行/何列連結しなければいけないかに応じて、その数だけ辺を張ればよい。

ll H,W;
vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H;
	FOR(i,W) cin>>x, V.push_back({x,0});
	FOR(i,H) cin>>x, V.push_back({x,1});
	
	sort(ALL(V));
	ll ret=0;
	W++;
	H++;
	FORR(r,V) {
		if(r.second==1) ret += W*r.first, H--;
		else ret += H*r.first, W--;
	}
	cout<<ret<<endl;
	
}

まとめ

すんなり解けて良かった。