なんでこんなストーリー設定にしたんだろう。
http://arc022.contest.atcoder.jp/tasks/arc022_3
問題
木を成す無向グラフが与えられる。
グラフの直径(2点間の最短路の最長距離)を成す2点を求めよ。
解法
幾つかやり方がある。
以下は自分の本番のやり方を紹介。
適当な点からDFSで求め、候補の点のペアのうち距離が最大のものを求めていく。
- 答えの2点の間のパスに現在見ている点が含まれる場合:
- 現在の点の各子について、それぞれ現在の点からの距離が最長のものを探す。上位2点を結んだものが直径候補。
- 子が1つしかない場合は、現在の点と子の先距離最長の点の対が候補。
- 答えの2点の間のパスに現在見ている点が含まれない場合:
- 各子についてそれぞれDFSを行い、子のツリー内で直径候補を求める。
別解として、最遠点を求めるDFSを2回行う手法があるようだ。
こちらはEditorial参照。
int N; vector<int> E[100001]; int sx,sy; int ma; pair<int,int> dfs(int cur,int pre) { vector<pair<int,int> > V; int i; FOR(i,E[cur].size()) { int tar=E[cur][i]; if(tar==pre) continue; V.push_back(dfs(tar,cur)); } V.push_back(make_pair(1,cur)); sort(V.begin(),V.end()); reverse(V.begin(),V.end()); if(V.size()>=2) { int tar=V[0].first+V[1].first; if(tar>ma) { ma=tar; sx=V[0].second+1; sy=V[1].second+1; } } return make_pair(V[0].first+1,V[0].second); } void solve() { int f,i,j,k,l,x,y; cin>>N; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } dfs(0,-1); _P("%d %d\n",sx,sy); }
まとめ
最遠点を2回求める方法は知らなかった…。