木の直径のテスト
(test/aoj/GRL_5_A.test.cpp)

• View this file on GitHub
• Last update: 2021-08-01 23:46:19+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A

Depends on

• graph/template.hpp
• 木の直径 (graph/tree-diameter.hpp)

Code

// @brief 木の直径のテスト
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A"

#include "../../graph/tree-diameter.hpp"

using namespace std;
#include <iostream>

int main() {
  int N; cin >> N;
  Graph< int > g(N);
  for(int i = 1; i < N; i++) {
    int x, y, z; cin >> x >> y >> z;
    g[x].emplace_back(x, y, z);
    g[y].emplace_back(y, x, z);
  }
  cout << tree_diameter(g) << endl;
}

#line 1 "test/aoj/GRL_5_A.test.cpp"
// @brief 木の直径のテスト
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A"

#line 1 "graph/tree-diameter.hpp"


// @title 木の直径

#include <utility>
#line 1 "graph/template.hpp"



#include <iostream>
#include <vector>

template< typename T >
struct Edge {
  int from, to;
  T cost;
  Edge() {}
  Edge(int f, int t) : from(f), to(t), cost(1) {}
  Edge(int f, int t, T c) : from(f), to(t), cost(c) {}
  friend bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.cost < rhs.cost; };
  friend bool operator > (const Edge& lhs, const Edge& rhs) { return rhs < lhs; };
  friend bool operator <= (const Edge& lhs, const Edge& rhs) { return !(lhs > rhs); };
  friend bool operator >= (const Edge& lhs, const Edge& rhs) { return !(lhs < rhs); };
};

template< typename T >
using Edges = std::vector< Edge< T > >;
template< typename T >
using Graph = std::vector< Edges< T > >;

template< typename T >
void debug(Graph<T> &g, int n = -1) {
    if (n == -1) n = g.size();
    for (int i = 0; i < n; ++i) {
        std::cerr << i  << "\t";
        for (auto &e: g[i]) {
            std::cerr << e.to << ",";
        }
        std::cerr << std::endl;
    }
}


#line 7 "graph/tree-diameter.hpp"

namespace tree_diameter_
{
template< typename T >
std::pair< T, int > dfs(const Graph<T> &g, int idx, int par) {
  std::pair< T, int > ret(0, idx);
  for(auto &e : g[idx]) {
    if(e.to == par) continue;
    auto cost = dfs(g, e.to, idx);
    cost.first += e.cost;
    ret = max(ret, cost);
  }
  return ret;
}

} // namespace tree_diameter

template< typename T >
T tree_diameter(const Graph<T> &g) {
  auto p = tree_diameter_::dfs(g, 0, -1);
  auto q = tree_diameter_::dfs(g, p.second, -1);
  return (q.first);
}


#line 5 "test/aoj/GRL_5_A.test.cpp"

using namespace std;
#line 8 "test/aoj/GRL_5_A.test.cpp"

int main() {
  int N; cin >> N;
  Graph< int > g(N);
  for(int i = 1; i < N; i++) {
    int x, y, z; cin >> x >> y >> z;
    g[x].emplace_back(x, y, z);
    g[y].emplace_back(y, x, z);
  }
  cout << tree_diameter(g) << endl;
}

Back to top page