hogloidのブログ

へなちょこ

Codeforces#148 div1C,div2E World Eater Brothers

URL:http://www.codeforces.com/contest/238/problem/C

問題概要

有向全域木が与えられる。2つ頂点を選んで、そこからすべての頂点へ辺の向きに従って到達できるように辺の向きを変える。
変えなければいけない辺の数をコストとすると、最小のコストはいくらか。

頂点数<=3000



















方針

2つの頂点で到達すればよいので、ある一つの辺で覆う範囲を分割できる。
分割した後は、
まずある頂点を選び、そこを始点としたとき分割したグラフ内で向きを変える辺の数(cost'と呼ぶ)を数える。
ここで、その選んだ頂点と隣接する頂点を始点とする向きを変える辺の数は、
最初に選んだ頂点が隣接する頂点に向いているなら、cost'+1
そうでないなら、cost'-1
となることが簡単に分かる。これはO(N)で実装できる

すべての辺で分割し、上の方針を繰り返す。O(N^2)

小さいケースに注意!

using namespace std;
static const int INF =500000000;

typedef pair<int,int> pi;
int n;
vector<pi> g[3005];
pi es[3005];
int dfs(int v,int p){
	int res=0;
	for(int i=0;i<g[v].size();++i){
		pi& e=g[v][i];
		if(e.first==p) continue;
		res+=e.second+dfs(e.first,v);
	}
	return res;
}
int move(int v,int p,int val){
	int res=val;
	for(int i=0;i<g[v].size();++i){
		pi& e=g[v][i];
		if(e.first==p) continue;
		res=min(res,move(e.first,v,val+1-e.second*2));
	}
	return res;
}

int main(){
	cin>>n;
	for(int i=0;i<n-1;++i){
		int a,b;cin>>a>>b;--a;--b;
		g[a].push_back(make_pair(b,0));
		g[b].push_back(make_pair(a,1));
		es[i]=make_pair(a,b);
	}
	int ans=INF;
	if(n<=2) ans=0;
	for(int i=0;i<n-1;++i){
		int A,B;
		A=es[i].first;B=es[i].second;

		int sum1=dfs(A,B),sum2=dfs(B,A);

		ans=min(ans,move(A,B,sum1)+move(B,A,sum2));
	}
	cout<<ans<<endl;


	return 0;
}

こういう回の場合、BよりCを先にやったほうが(解ける人にとっては)いいです