会津大学オンラインジャッジ 問 Tree - Diameter of a Tree

Tree - Diameter of a Tree

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A
グラフ理論における木の直径をこたえる問題。


解法
一点を根元と定めて木を探索します。
深さ優先探索で木を旅する旅人を考えます。
枝先まで旅をします。
枝先にぶち当たったら戻りますが戻るとき距離を数えて、枝先からここまでの距離を分岐ごとに点に記録しておきます。
この分岐の先で一番遠かった枝先までの距離は何々だとします。

ある点の枝先を全部調べ終えたら帰るとき、枝先で一番距離が遠かったものをその道の最も長い距離だと根元側の点に記録します。
これを繰り返してスタート地点まで戻ってくれば答えです。

途中の点で二つの枝先の距離合計が最も遠くなる点を計算する場合を忘れないようにします。

私のコードは試行錯誤の後が残ってるので少し無駄な処理が入っていますが答えには影響しません。
一応コード実行速度で一位に並びました。
こういう綺麗な問題は解いてて楽しいですが、順位差をつけにくいのが欠点ですね。



#include<stdio.h>
#include<vector>
#include<map>
#include<stack>
struct E{
      int t,w,old;
      bool first;
};
const int LIMIT=100001;
std::vector<E> G[LIMIT];
int ans=0;

int sumMax[LIMIT]={0},sumSecond[LIMIT]={0},nowMax[LIMIT]={0};
void setSumMax(int p,int w){
      if(sumMax[p]<=w){
            sumSecond[p]=sumMax[p];
            sumMax[p]=w;
      }else if(sumSecond[p]<=w){
            sumSecond[p]=w;
      }
}


void calc(){
      std::stack<E> sta;
   
      E e1,e2;
      e1.t=0;
      e1.old=-1;
      e1.w=0;
      e1.first=true;
      sta.push(e1);
      int ans=0,c=0;
      while(sta.empty()==false){
            e1=sta.top();
            sta.pop();
            int p=e1.t;
            if(e1.first==true){
                  e1.first=false;
                  sta.push(e1);
            }else{
                  int resultMax=sumMax[p]+e1.w;
                  setSumMax(p,nowMax[p]);
                  ans=std::max(ans,sumMax[p]+sumSecond[p]);
                  setSumMax(e1.old,resultMax);
                  continue;
            }
         
            std::vector<E>::iterator vIt,vItEnd;
            vItEnd=G[p].end();
            for(vIt=G[p].begin();vIt!=vItEnd;vIt++){
                  e2=(*vIt);
                  e2.first=true;
                  if(e2.t==e1.old)continue;
                  sta.push(e2);
                  nowMax[e2.t]=nowMax[e1.t]+e2.w;
            }
      }
      printf("%d\n",ans);
}

int main(){
      int n,s,t,w;
      E e1,e2;
      scanf("%d",&n);
   
      for(int i=1;i<n;i++){
            scanf("%d %d %d",&s,&t,&e1.w);
            e1.t=t;
            e1.old=s;
            G[s].push_back(e1);
            e1.t=s;
            e1.old=t;
            G[t].push_back(e1);
      }
      calc();
}