Codeforces 283C - World Eater Brothers

問題文 : World Eater Brothers

問題概要 :

$N$ 頂点からなる有向全域木$G$ が与えられる. 高々2 つの頂点を選んで, この頂点から他の頂点への有向パスが存在するようにするために変えなければならない辺の向きの最小値を求めよ.

$N \leqq 3000$

解法 :
まず$N \leqq 2$ のときは辺の向きを変える必要がない.

$N \geqq 3$ のときを考える. 2 つの頂点$u,\ v$ を選んで2 つの全域木の集合に分けるということを考えると, 全域木の中の1 本の辺を切断していると考えることができるので, まずは切断する辺を全て試す事を考える.

切断した辺の端点となっている頂点を根として$O(N)$ 時間でdfs をすることで, 端点を頂点としたときに必要な辺の向きの変更コストが求まる(このコストを$c$ とする). 端点が最適値を与えない場合を考えると, 隣接する頂点を新たな木の根にすることを全ての頂点について試せば良いことが分かる. コストが$c$ だったときに, 辿る先の辺が元の向きと同じ辺であれば新たなコストは$c+1$, 逆辺であれば$c-1$ となる.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int> > G[4096];

int dfs(int v, int p)
{
	int ret = 0;
	for (int i = 0; i < G[v].size(); i++){
		if (G[v][i].first != p){
			ret += G[v][i].second + dfs(G[v][i].first, v);
		}
	}
	return (ret);
}

int decideCenter(int v, int p, int c)
{
	int ret = c;
	for (int i = 0; i < G[v].size(); i++){
		if (G[v][i].first != p){
			ret = min(ret, decideCenter(G[v][i].first, v, c + 1 - 2 * G[v][i].second));
		}
	}
	return (ret);
}

int main()
{
	int N;
	
	scanf("%d", &N);
	
	for (int i = 0; i < N - 1; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		G[--a].push_back(make_pair(--b, 0));
		G[b].push_back(make_pair(a, 1));
	}
	
	int ans = max(0, N - 2);
	
	for (int i = 0; i < N; i++){
		for (int j = 0; j < G[i].size(); j++){
			int c1 = dfs(i, G[i][j].first);
			int c2 = dfs(G[i][j].first, i);
			
			ans = min(ans, decideCenter(i, G[i][j].first, c1) + decideCenter(G[i][j].first, i, c2));
		}
	}
	
	printf("%d\n", ans);
	
	return (0);
}