위 포스트는 백준 8872 - 빌라봉 문제의 해설입니다.

핵심 아이디어#

위 문제에는 여러 개의 트리가 존재한다.
임의의 2개의 트리를 서로 이을 때 최대 시간이 최소가 되게 하기 위해서는 각 트리의 지름에서 중간점을 찾아, 그 중간점끼리 연결해야 최대시간이 최소가 될 것이다.

또한 각 트리끼리의 이동 시간의 최대시간을 최소로 만들려면 트리의 지름이 가장 큰 애와 나머지 트리를 서로 연결해야 할 것이다.

따라서 정답은 결국 3개 중 하나가 된다. (지름이 가장 긴 순서대로 번호가 매겨졌을 때라 가정하자.)

1. 1번 트리의 지름
2. 1번 트리 - L - 2번 트리
   $(1번 트리의 반지름) + L + (2번 트리의 반지름)$
3. 2번 트리 - L - L - 3번 트리
   $(2번 트리의 반지름) + 2L + (3번 트리의 반지름)$

코드#

cpp
1#include <bits/stdc++.h>
2
3#define endl "\n"
4#define all(v) (v).begin(), (v).end()
5#define all1(v) (v).begin()+1, (v).end()
6#define For(i, a, b) for(int i=(a); i<(b); i++)
7#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
8#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)
9#define BOR(i, a, b) for(int i=(a); i>=(b); i--)
10#define ft first
11#define sd second
12
13using namespace std;
14using ll = long long;
15using lll = __int128_t;
16using ulll = __uint128_t;
17using ull = unsigned long long;
18using ld = long double;
19using pii = pair<int, int>;
20using pll = pair<ll, ll>;
21using ti3 = tuple<int, int, int>;
22using tl3 = tuple<ll, ll, ll>;
23
24template<typename T> using ve = vector<T>;
25template<typename T> using vve = vector<vector<T>>;
26
27template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
28template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
29
30const int INF = 987654321;
31const int INF0 = numeric_limits<int>::max();
32const ll LNF = 987654321987654321;
33const ll LNF0 = numeric_limits<ll>::max();
34
35ll n, m, l;
36vve<pll> g;
37ve<bool> vis;
38
39ll U, D;
40void dfs(ll p, ll u, ll d) {
41    vis[u] = true;
42    if(D < d) {
43        U = u;
44        D = d;
45    }
46    for(auto [v,w] : g[u]) {
47        if(v == p) continue;
48        dfs(u, v, d+w);
49    }
50}
51ve<pll> route;
52bool path(ll p, ll u, ll dst) {
53    if(u == dst) {
54        return true;
55    }
56    for(auto [v,w] : g[u]) {
57        if(v == p) continue;
58        route.emplace_back(v, route.back().sd + w);
59        if(path(u,v,dst)) return true;
60        route.pop_back();
61    }
62    return false;
63}
64bool cmp(ll a, ll b) { return a > b; }
65
66void solve() {
67    cin >> n >> m >> l;
68    g = vve<pll>(n+1);
69    vis = ve<bool>(n+1, false);
70    while(m--) {
71        ll a, b, t; cin >> a >> b >> t;
72        g[a].emplace_back(b,t);
73        g[b].emplace_back(a,t);
74    }
75
76    ll ans = 0;
77    ve<ll> maxs;
78    for(int i=0; i<n; i++) {
79        if(vis[i]) continue;
80
81        D = -1;
82        dfs(i,i,0);
83        ll A = U;
84
85        D = -1;
86        dfs(A,A,0);
87        ll B = U;
88        ll AB_dist = D;
89
90        ckmax(ans, AB_dist);
91
92        route.clear();
93        route.emplace_back(A,0);
94        path(A,A,B);
95
96        int j=0;
97        while(j < route.size()-1) {
98            if(max(route[j].sd, AB_dist-route[j].sd) < max(route[j+1].sd, AB_dist-route[j+1].sd)) break;
99            j++;
100        }
101        maxs.emplace_back(max(route[j].sd, AB_dist-route[j].sd));
102    }
103    sort(all(maxs), cmp);
104    if(maxs.size() >= 2) ckmax(ans, maxs[0] + maxs[1] + l);
105    if(maxs.size() > 2) ckmax(ans, maxs[1] + maxs[2] + l*2);
106
107    cout << ans << endl;
108}
109
110int main(void) {
111    ios_base::sync_with_stdio(false);
112    cin.tie(nullptr);
113    cout.tie(nullptr);
114
115    int TC=1;
116//    cin >> TC;
117    FOR(tc, 1, TC) {
118//        cout << "Case #" << tc << ": ";
119        solve();
120    }
121
122
123    return 0;
124}