[IOI2013 Day1] Dreaming 해법

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/dreaming/Dreaming ko (KOR).pdf

$N-M-1$개의 간선을 새로 추가하고 나서 답이 될 수 있는 경우는 다음과 같다.

1. 기존의 트리에 있는 최장 경로
2. 새로운 간선이 포함되는 최장 경로

1번 경우를 계산하기 위해, 우리는 트리 내의 최장 경로의 길이를 구해야한다. 트리 내에 최장 경로를 트리의 '지름'이라고 말한다. 트리의 지름 구하는 방법은 여러가지가 존재하는데, 그 중 하나는 어떤 한 정점을 잡고, 그 점과 가장 먼 점 $v$를 찾고, 다시 $v$ 에서 제일 먼 경로를 찾으면 그 경로가 트리의 지름이 된다. 처음에 기존에 있는 트리들의 지름을 구하고 답으로 갱신한다.

2번 경우 해결을 위한 설명의 편의상 트리의 '반지름'을 정의하겠다. 어떤 정점 $v$와 가장 먼 정점과의 거리들 중 최소 길이를 '반지름의 길이'라 하며 이 때 정점 $v$를 트리의 '중심'이라 정의하겠다. 입력으로 주어진 트리들의 반지름 길이를 내림차순으로 정렬한다.

반지름들을 $r_1$ ≥ $r_2$ ≥ ... ≥ $r_k$ 라고 하자.

$k>1$인 경우, $r_1+r_2+L$을 답으로 갱신해주고
$k>2$인 경우, $r_2+r_3+2L$을 답으로 갱신해준다.

즉, $r_1$의 중심 노드와 각 트리의 중심 노드를 연결해준 꼴이 된다.
중심들끼리 연결해야 됨은 자명하고, 중심들을 이처럼 연결해주는 것이 2번 경우 최대값을 최소화 할 수 있음은 쉽게 증명된다.

#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define pb push_back typedef pair<int, int> pii; int N, M, L, K; int D[MAXN], E[MAXN], G[MAXN], R[MAXN]; int par[MAXN]; vector <pii> con[MAXN]; void dfs(int n) { G[n] = K; for (pii &p: con[n]){ int t = p.first, v = p.second; if (t == par[n]) continue; par[t] = n; dfs(t); E[n] = max(E[n], E[t]+v); } } void dfs2(int n, int d) { int mx1 = d, mx2 = 0; for (pii &p: con[n]){ int t = p.first, v = p.second; if (t == par[n]) continue; if (mx1 < E[t]+v) mx2 = mx1, mx1 = E[t]+v; else if (mx2 < E[t]+v) mx2 = E[t]+v; } D[n] = mx1; for (pii &p: con[n]){ int t = p.first, v = p.second; if (t == par[n]) continue; dfs2(t, (E[t]+v == mx1 ? mx2 : mx1)+v); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { ::N = N, ::M = M, ::L = L; for (int i=0;i<M;i++){ int a = A[i]+1, b = B[i]+1, c = T[i]; con[a].pb({b, c}); con[b].pb({a, c}); } for (int i=1;i<=N;i++) if (!par[i]){ par[i] = i; K++; dfs(i); } for (int i=1;i<=N;i++) if (par[i] == i) dfs2(i, 0); for (int i=1;i<=K;i++) R[i] = 2e9; for (int i=1;i<=N;i++) R[G[i]] = min(R[G[i]], D[i]); int ans = 0; for (int i=1;i<=N;i++) ans = max(ans, D[i]); sort(R+1, R+K+1, greater<int>()); if (K > 1) ans = max(ans, R[1]+R[2]+L); if (K > 2) ans = max(ans, R[2]+R[3]+L+L); return ans; }