P4408 [NOI2003]逃学的小孩

题目描述

Chris家的电话铃响起了，里面传出了Chris的老师焦急的声音：“喂，是Chris的家长吗？你们的孩子又没来上课，不想参加考试了吗？”一听说要考试，Chris的父母就心急如焚，他们决定在尽量短的时间内找到Chris。他们告诉Chris的老师：“根据以往的经验，Chris现在必然躲在朋友Shermie或Yashiro家里偷玩《拳皇》游戏。现在，我们就从家出发去找Chris，一但找到，我们立刻给您打电话。”说完砰的一声把电话挂了。

Chris居住的城市由N个居住点和若干条连接居住点的双向街道组成，经过街道x需花费Tx分钟。可以保证，任两个居住点间有且仅有一条通路。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（3 ≤ N ≤ 200000）和M，分别表示居住点总数和街道总数。

以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1≤Ui, Vi ≤ N，1 ≤ Ti ≤ 1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。街道信息不会重复给出。

输出格式

输出文件仅包含整数T，即最坏情况下Chris的父母需要花费T分钟才能找到Chris。

输入输出样例

输入 #1

输出 #1

4
题意：给一棵无根树，选出A,B,C三个点使得AB+BC最大。
分析：先求出树的直径，再分别从直径的两个端点开始dfs，找到每个点到直径端点的距离。令直径端点为A,B,则答案为dis[A][B]+
max(min(dis[A][k],dis[B][k])) (k是除了AB之外的点)
　　　还要注意开longlong

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 200000+5;
 4 typedef long long ll;
 5 struct Node{
 6     int to, dis, next;
 7 }edge[maxn << 1];
 8 ll head[maxn], cnt, p1, p2, t, ans, f[maxn][3];
 9 int n, m;
10 void Add(int u, int v, int w){
11     edge[++cnt].to = v;
12     edge[cnt].next = head[u];
13     edge[cnt].dis = w;
14     head[u] = cnt;
15 }
16 void Dfs(int rt, int fa, ll sum){
17     if (ans < sum){
18         ans = sum;
19         t = rt;
20     }
21     for (int i = head[rt]; i; i = edge[i].next){
22         int v = edge[i].to, dis = edge[i].dis;
23         if (v != fa){
24             Dfs(v, rt, sum + dis);
25         }
26     }
27 }
28 void Dfs1(int rt, int fa, int k){
29     for (int i = head[rt]; i; i = edge[i].next){
30         int v = edge[i].to, dis = edge[i].dis;
31         if (v == fa) continue;
32         f[v][k] = f[rt][k] + dis;
33         Dfs1(v, rt, k);
34     }
35 }
36 int main(){
37     scanf("%d%d", &n, &m);
38     for (int i = 1; i <= m; i++){
39         int u, v, w;
40         scanf("%d%d%d", &u, &v, &w);
41         Add(u, v, w);
42         Add(v, u, w);
43     }
44     Dfs(1, 0, 0);
45     p1 = t; ans = 0;
46     Dfs(p1, 0, 0);
47     p2 = t;
48     Dfs1(p1, 0, 1);
49     Dfs1(p2, 0, 0);
50     ll ans1 = 0;
51     for (int i = 1 ; i <= n; i++){
52         ans1 = max(ans1, min(f[i][0], f[i][1]));
53     }
54     printf("%lld", ans1 + ans);
55     return 0;
56 }

View Code