これもすんなり目途がたった。
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; } }
まとめ
コード量は若干多いけど、どれも典型。