AOJ 2382

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2382

証明がむずい。地雷。絶対450じゃない。数オリメダリストの力を借りました。

まず隣接してる頂点同士を結んで木を作ります。この木の辺の数をfとしましょう。
f=N-1の時、全ての頂点が直接的or間接的につながっていることになります。
その時、適当な点を根として葉からスライムを合成していけば操作はN-1回となります。
1回の操作でスライムの数はたかだか1個しか減らないのでこれが最小です。

f≠N-1としましょう。
最小回数は壁に頂点がある時2N-f-2、ない時2N-f-1であることを示しましょう。

まずN=2です。
壁にスライムがあったら、スライムがある壁にもうひとつのスライムを移動させてから合成すればいいので2回、
壁にスライムがなかったら、2つのスライムを同じ壁に追いやってから合成させればいいので3回です。
主張は成立してます。

今度はあるN(>=2)の時、上の主張が成立するとして、N+1について考えましょう。
あるスライムを動かして頂点の数がN+1からNに減少したとします。
このときf->f-1、N+1->Nとなり、Nの場合に帰着できます。よって、操作の回数は
1+2*N-(f-1)-(1or2)=2*(N+1)-f-(1or2)となり成立です。
今度は頂点の数がN+1からN+1となった時、つまり合成が起こらなかった時を考えます。
ちょっとややこしいですが、考えるとfはせいぜい1しか増えないことがわかります。
1回操作したのに、(-f)での減少効果も1しか得られないので、N+1→N+1にする操作をしても操作の回数が2(N+1)-f-(1or2)よりも
小さくならないことが言えます。

アー結局ここまで書いたのに雑になってしまいました…fが1しか増えないことを示すのも意外にややこしい。図を書けばなんとなく
わかるんですが。
あとN+1->Nに合成する時スライムが壁から離れないようにしないといけませんが、これもf=0で場合分けがあってめんどくさい。

だれか証明完成させてください…おねがいします…

int N, H, W;
vector<int> G[300010];
bool used[300010];

void loop(int v) {
	used[v] = true;
	rep(i, G[v].size()) {
		int n = G[v][i];
		if(!used[n]) loop(n);
	}
}

int main() {
	cin >> N >> H >> W;
	bool wall = false;
	rep(i, N) {
		int a, b; cin >> a >> b; a--; b--;
		if(a == 0 || a == H - 1 || b == 0 || b == W - 1) wall = true;
		G[i].pb(a + N);
		G[a + N].pb(i);
		G[i].pb(b + N + 100000);
		G[b + N + 100000].pb(i);
	}
	int K = 0;
	rep(i, N) {
		if(!used[i]) {
			loop(i); K++;
		}
	}
	if(K == 1) cout << N - 1 << "\n";
	else cout << N + K - (wall ? 2 : 1) << "\n";
}

オマケでshortest code達成しておきました。