[NOI2003] 逃學的小孩

題目描述

Chris 家的電話鈴響起了，里面傳出了 Chris 的老師焦急的聲音：“喂，是 Chris 的家長嗎？你們的孩子又沒來上課，不想參加考試了嗎？”一聽說要考試，Chris 的父母就心急如焚，他們決定在盡量短的時間內找到 Chris。他們告訴 Chris 的老師：“根據以往的經驗，Chris 現在必然躲在朋友 Shermie 或 Yashiro 家里偷玩《拳皇》游戲。現在，我們就從家出發去找 Chris，一但找到，我們立刻給您打電話。”說完砰的一聲把電話掛了。

Chris 居住的城市由 $N$ 個居住點和若干條連接居住點的雙向街道組成，經過街道 $x$ 需花費 $T_x$ 分鐘。可以保證，任兩個居住點間有且僅有一條通路。Chris 家在點 $C$，Shermie 和 Yashiro 分別住在點 $A$ 和點 $B$。Chris 的老師和 Chris 的父母都有城市地圖，但 Chris 的父母知道點 $A$、$B$、$C$ 的具體位置而 Chris 的老師不知。

為了盡快找到 Chris，Chris 的父母會遵守以下兩條規則：

如果 $A$ 距離 $C$ 比 $B$ 距離 $C$ 近，那么 Chris 的父母先去 Shermie 家尋找 Chris，如果找不到，Chris 的父母再去 Yashiro 家；反之亦然。

Chris 的父母總沿著兩點間唯一的通路行走。

顯然，Chris 的老師知道 Chris 的父母在尋找 Chris 的過程中會遵守以上兩條規則，但由于他并不知道 $A$、$B$、$C$ 的具體位置，所以現在他希望你告訴他，最壞情況下 Chris的父母要耗費多長時間才能找到 Chris？

輸入格式

輸入文件第一行是兩個整數 $N$ 和 $M$，分別表示居住點總數和街道總數。

以下 $M$ 行，每行給出一條街道的信息。第 $i+1$ 行包含整數 $U_i$、$V_i$、$T_i$，表示街道 $i$ 連接居住點 $U_i$ 和 $V_i$，并且經過街道 $i$ 需花費 $T_i$ 分鐘。街道信息不會重復給出。

輸出格式

輸出文件僅包含整數 $T$，即最壞情況下 Chris 的父母需要花費 $T$ 分鐘才能找到 Chris。

樣例 #1

樣例輸入 #1

4 3 1 2 1 2 3 1 3 4 1

樣例輸出 #1

4

提示

對于 $100\%$ 的數據，$3\le N\le 2\times 10^5$，$1\le U_i,V_i\le N$，$1\le T_i\le 10^9$。

1、 兩次DFS 求樹的直徑隨便選擇一個點（假如是1）， 求出所有點與1 的距離 d[k], 取一個點A ,使得d[A] 最大。那么A點一定是樹的直徑的一個端點。然后以A為頂點，求出所有點與A的距離 d[k]( 1 <= k <= n), 取一個點B ,使得d[B] 最大.點A 和B之間的路徑一定是樹的直徑。 2、題目的答案就是 找到一個點k, 先從k點走到A點，然后從A點走到B點，距離 = dAK（或者dBK） + dAB; 總而言之，直徑dAB 是必須走的距離。 題目要求 k點走到 A 或者 B的距離取較小值，ans = max{dAB + min(dAk, dBk)} 3、 開兩個距離數組 ll d1[N], d2[N];ll d1[N]; // A 點的距離數組ll d2[N]; // B 點的距離數組最后遍歷一下，取 max{ min(d1[k], d2[k])} 即可

算法競賽進階指南，圖論習題 9

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 10, M = 4e5 + 10; int head[N], ver[M], Next[M], edge[M]; int n, m, tot; ll d1[N], d2[N]; int A, B; //樹的直徑的兩個端點 bool vis[N]; ll maxlen; ll d0[N];void add(int x, int y, int z) {ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot; }void dfs(int x, ll d[]) {vis[x] = true;for(int i = head[x]; i; i = Next[i]){int y = ver[i];if(!vis[y]){d[y] = d[x] + edge[i]; dfs(y, d);}} }// ans = max{dAB + min(dAk, dBk)} void calc() {ll ans = 0; for(int i = 1; i <= n; ++i){if(i != A && i != B){// printf("d1[%d] = %d, d2[%d] = %d\n", i, d1[i], i, d2[i]);ll tmp = min(d1[i], d2[i]);ans = max(tmp, ans);}} // printf("d1[B] = %d\n", d1[B]);ans += d1[B];printf("%lld\n", ans); }int main() {scanf("%d%d", &n, &m);int x, y, z; for(int i = 0; i < m; ++i){scanf("%d%d%d", &x, &y, &z);add(x, y, z); add(y, x, z);}dfs(1, d0);for(int i = 1; i <= n; ++i){if(maxlen < d0[i]){maxlen = d0[i];A = i;}}memset(vis, false, sizeof vis);dfs(A, d1);maxlen = 0;for(int i = 1; i <= n; ++i){if(maxlen < d1[i]){maxlen = d1[i];B = i;}}memset(vis, false, sizeof vis);dfs(B, d2);//找到樹的直徑的兩個端點 A, Bcalc();return 0; }

總結

以上是生活随笔為你收集整理的洛谷 P4408 [NOI2003] 逃学的小孩（树的直径）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。