kmjp's blog

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

TopCoder SRM 635 Div2 Hard LonglongestPathTree

これもすんなり目途がたった。
http://community.topcoder.com/stat?c=problem_statement&pm=13416

問題

長さ付き辺で構成されるN頂点の木を成すグラフが与えられる。
(N-1)辺のうち1個を外し、同じ長さの辺を別の2頂点間に追加して再び全体を連結グラフにするとき、最長の木の直径を答えよ。

解法

木の直径をO(|V|)で求める方法は下記の通り既出。
AtCoder ARC #022 : C - ロミオとジュリエット - kmjp's blog

1つの解の候補は、辺をどう付け替えても直径は長くならない、すなわち初期状態の直径がすでに最長。

後は付け替える辺を総当たりで選択していく。
付け替える辺を選んだら、付け替え後の最長直径は(付け替えにより分断された2つの木それぞれの直径の和)+(付け替える辺の長さ)となる。
あとはこの値の最大値を求めればよい。O(N^2)で済む。

class LonglongestPathTree {
	public:
	ll ma;
	int N,unavail[2];
	vector<pair<int,ll> > E[2001];
	ll D[2001];
	int far;
	
	void dfs(int cur,int pre) {
		int i;
		FOR(i,E[cur].size()) if(E[cur][i].first!=pre) {
			int tar=E[cur][i].first;
			if(cur==unavail[0] && tar==unavail[1]) continue;
			if(cur==unavail[1] && tar==unavail[0]) continue;
			D[tar]=D[cur]+E[cur][i].second;
			if(D[tar]>D[far]) far=tar;
			dfs(tar,cur);
		}
	}
	
	ll dia(int cur) {
		far=cur;
		D[cur]=0;
		dfs(cur,-1);
		cur=far;
		D[cur]=0;
		dfs(cur,-1);
		return D[far];
	}
	
	
	long long getLength(vector <int> A, vector <int> B, vector <int> L) {
		int i;
		N=A.size()+1;
		FOR(i,N) E[i].clear();
		FOR(i,N-1) {
			E[A[i]].push_back(make_pair(B[i],L[i]));
			E[B[i]].push_back(make_pair(A[i],L[i]));
		}
		
		unavail[0]=unavail[1]=-1;
		ma=dia(0);
		FOR(i,N-1) {
			unavail[0]=A[i];
			unavail[1]=B[i];
			ma=max(ma,dia(A[i])+dia(B[i])+L[i]);
		}
		return ma;
		
	}
}

まとめ

コード量は若干多いけど、どれも典型。