首页 > 代码库 > 1509: [NOI2003]逃学的小孩 - BZOJ

1509: [NOI2003]逃学的小孩 - BZOJ

2024-07-06 10:17:48   228人阅读

Description


Input

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

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

4 3

1 2 1

2 3 1

3 4 1

Sample Output

4

 

 

树dp

其实不是很难，只是要小心细节

我们要找出一个三叉路（允许一条为0）从大到小为a，b，c，使得a+b+b+c最大

所以我们先树dp求出每个点往下走的最长的三条边，但是这条边还可能来自于父亲，所以再dfs一遍，然后更新答案

 1 const
 2     maxn=200200;
 3 var
 4     first,u:array[0..maxn]of longint;
 5     next,last,w:array[0..maxn*2]of longint;
 6     f:array[0..maxn,0..3]of int64;
 7     n,m,tot:longint;
 8     ans:int64;
 9 
10 procedure insert(x,y,z:longint);
11 begin
12     inc(tot);
13     last[tot]:=y;
14     next[tot]:=first[x];
15     first[x]:=tot;
16     w[tot]:=z;
17 end;
18 
19 procedure up(var x:int64;y:int64);
20 begin
21     if x<y then x:=y;
22 end;
23 
24 procedure new(x:longint;y:int64);
25 begin
26     if y>f[x,0] then
27       begin
28         f[x,2]:=f[x,1];
29         f[x,1]:=f[x,0];
30         f[x,0]:=y;
31       end
32     else
33       if y>f[x,1] then
34         begin
35           f[x,2]:=f[x,1];
36           f[x,1]:=y;
37         end
38       else up(f[x,2],y);
39 end;
40 
41 procedure dfs(x,fa:longint);
42 var
43     i:longint;
44 begin
45     i:=first[x];
46     while i<>0 do
47       begin
48         if last[i]<>fa then
49         begin
50           dfs(last[i],x);
51           u[last[i]]:=w[i];
52           new(x,f[last[i],0]+w[i]);
53         end;
54         i:=next[i];
55       end;
56 end;
57 
58 function get(x,y,z:int64):int64;
59 begin
60     exit(x+y*2+z);
61 end;
62 
63 procedure dfs2(x,fa:longint);
64 var
65     i:longint;
66 begin
67     if f[x,0]+u[x]=f[fa,0] then new(x,f[fa,1]+u[x])
68     else new(x,f[fa,0]+u[x]);
69     up(ans,get(f[x,0],f[x,1],f[x,2]));
70     i:=first[x];
71     while i<>0 do
72       begin
73         if last[i]<>fa then dfs2(last[i],x);
74         i:=next[i];
75       end;
76 end;
77 
78 procedure main;
79 var
80     i,x,y,z:longint;
81 begin
82     read(n,m);
83     for i:=1 to m do
84       begin
85         read(x,y,z);
86         insert(x,y,z);
87         insert(y,x,z);
88       end;
89     dfs(1,0);
90     dfs2(1,0);
91     write(ans);
92 end;
93 
94 begin
95     main;
96 end.
View Code

 


联系
我们