POJ 1985 Cow Marathon

問題

無向木の情報が与えられる。同じ辺を2度辿らないように頂点間を移動する時、もっとも距離の遠い2点間の距離を求めよ。

やりかた

無向木の直径を求める問題に他ならない。直径の求め方は、てきとうな頂点から深さ優先探索を始めて最遠の頂点uを求める。つづいてその最遠の頂点uから始めて、最遠の頂点vを求める。するとu-vの頂点間が最遠の距離になっている。

以下ソース。

struct edge{
  int to, cost;
};

vector<edge> g[40001];
int dist[40001];

void dfs(int cur, int prev, int cost){
  dist[cur] = cost;
  for(int i = 0; i < g[cur].size(); i++)
    if(g[cur][i].to != prev) 
      dfs(g[cur][i].to, cur, cost + g[cur][i].cost);
}

int main(int argc, char **argv){
  int V, E;
  scanf("%d %d", &V, &E);

  for(int i = 0; i < E; i++){
    int s, t, c; char dir;
    scanf("%d %d %d %c", &s, &t, &c, &dir);
    g[s - 1].push_back((edge){t - 1, c});
    g[t - 1].push_back((edge){s - 1, c});
  }

  fill(dist, dist + V, 0);
  dfs(0, -1, 0);;

  int u = max_element(dist, dist + V) - dist;
  fill(dist, dist + V, 0);
  dfs(u, -1, 0);
  printf("%d\n", *max_element(dist, dist + V));
  return 0;
}