洛谷 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。

输入输出样例

输入样例

View Code

输出样例

分析

我们要从点C出发先走到点A再走到点B(CA<CB) 或者是从点C出发先走到点B再走到点A(CB<CA)

其实这两种情况是一样的，因为A、B的位置我们不确定，所以两点可以互换，所以我们把题目简化：

一句话题意：在一棵树上找三个点A、B、C使得AB+AC的值最大（满足AC<=BC）

这道题可以说是一个模板题，虽然题目中又是逃学又是找人，但实际上是让你求树的直径

AB的最大值很好想，显然就是树的直径，在一棵树中没有比直径更长的路程了

那么AC的最大值呢，我们可以在dfs求树的直径的时候顺便把每一个点到A、B的价值都求出来，在这两个价值中取较小值（因为要先到比较近的点）

最后再枚举一遍求最优决策（最大值），这实际上是一种贪心的思想

我们引用一下洛谷上的证明：传送门

最后要注意几个细节：

1、开long long，并且赋值为无穷大时要写8个3f：0x3f3f3f3f3f3f3f3f

2、双向边，开数组时一定要乘2

3、数组不能开得太大

这三个细节我每个都错了一遍

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 const int maxn=500010;//数组不要开小了
 8 typedef long long ll;//记得开long long
 9 struct asd{
10     ll from,to,next,val;
11 }b[maxn];
12 ll n,m;
13 ll head[maxn],tot=1;
14 void ad(ll aa,ll bb,ll cc){
15     b[tot].from=aa;
16     b[tot].to=bb;
17     b[tot].next=head[aa];
18     b[tot].val=cc;
19     head[aa]=tot++;
20 }//加边函数
21 ll dis[maxn],disA[maxn],disB[maxn],A,B;
22 //disA是每个点到端点A的距离,disB是，每个点到端点B的距离
23 //A、B为端点A、B的编号
24 ll zhijing,jl=-0x3f3f3f3f3f3f3f3f,id=0;//定义直径
25 void dfs(ll now,ll fa){
26     for(ll i=head[now];i!=-1;i=b[i].next){
27         ll u=b[i].to;
28         ll da=b[i].val;
29         if(u==fa) continue;
30         dis[u]=dis[now]+da;
31         if(dis[u]>jl){
32             jl=dis[u];
33             id=u;
34         }
35         dfs(u,now);
36     }
37 }//dfs求直径
38 int main() {
39     scanf("%lld%lld",&n,&m);
40     memset(head,-1,sizeof(head));
41     for(ll i=1;i<=m;i++){
42         ll aa,bb,cc;
43         scanf("%lld%lld%lld",&aa,&bb,&cc);
44         ad(aa,bb,cc);
45         ad(bb,aa,cc);
46     }
47     dfs(1,0);//第一遍dfs求A点标号
48     A=id;
49     memset(dis,0,sizeof(dis));
50     id=0,jl=-0x3f3f3f3f3f3f3f3f;
51     dfs(A,0);//第二遍dfs求B点标号以及每一个点到A点的距离
52     B=id,zhijing=jl;
53     id=0,jl=-0x3f3f3f3f3f3f3f3f;
54     for(ll i=1;i<=n;i++){
55         disA[i]=dis[i];
56     }
57     memset(dis,0,sizeof(dis));
58     dfs(B,0);//第三遍dfs求每一个点到B点的距离，每次dfs之前不要忘了初始化
59     for(ll i=1;i<=n;i++){
60         disB[i]=dis[i];
61     }
62     ll ans=-0x3f3f3f3f3f3f3f3f;
63     for(ll i=1;i<=n;i++){
64         ans=max(ans,min(disA[i],disB[i]));
65     }//求最最优决策
66     printf("%lld
",ans+zhijing);//输出
67     return 0;
68 }

View Code