编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 166ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：435ms

小小改动：

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

再一改（纯属想象）：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

过程流

纪念提交第100道题

AC的第50道

难度为3

太高兴啦！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：387ms

type

integer=longint;

var

x,y,m,max,min,ma,fa,a,b,c,i,j,k,l,n,t,s,o:integer;

g,d,v,next,ks,e:array[1..600]of integer;

p,f:array[1..300,1..300]of int64;

procedure int;

begin

readln(n,s);

for i:=1 to n do for j:=1 to n do f:=maxlongint;

for i:=1 to n-1 do

begin

readln(a,b,c);

inc(t);next[t]:=ks[a];ks[a]:=t;e[t]:=b;g[t]:=c;

inc(t);next[t]:=ks;ks:=t;e[t]:=a;g[t]:=c;

f[a,b]:=c;f:=c;

end;

end;

procedure floyed;

var

i,j,k:integer;

begin

for k:=1 to n do

for i:=1 to n do

if ki then

for j:=1 to n do

if(jk)and(ji)then

if f+f[k,j]max then begin max:=m;fa:=i;end;

end;

procedure dfs1(i,j:integer);

begin

if p=0then begin inc(o);d[o]:=j;end

else

begin

dfs1(i,p);dfs1(p,j);

end;

end;

procedure meiju;

var a,b:array[1..300]of integer;

begin

min:=maxlongint;

for i:=1 to o do

for j:=i to o do

begin

if(f[d[i],d[j]]

单调队列真好用

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program core2;

var

h,r,t,min,maxt,m,head,rear,x,y,s,n,i,j,k:longint;

v:array[0..500]of boolean;

a:array[0..300,0..300]of longint;

l,q,d,p:array[0..500]of longint;

procedure dfs(x,aim:longint);

begin

if xaim

then begin

inc(m);

l[m]:=x;

dfs(p[x],aim);

end;

end;

function bfs(x:longint):longint;

var y,i,j,k,h,r:longint;

begin

fillchar(v,sizeof(v),true);

fillchar(d,sizeof(d),0);

fillchar(q,sizeof(q),0);

p:=q;

h:=1; r:=2;

q[h]:=x;

v[x]:=false;

while hd[bfs] then bfs:=i;

end;

begin

assign(input,'core.in'); reset(input);

assign(output,'core.out'); rewrite(output);

fillchar(a,sizeof(a),$3f);

readln(n,s);

for i:=1 to n-1 do begin

read(x,y);

readln(a[x,y]);

a[y,x]:=a[x,y];

end;

for i:=1 to n do a:=0;

head:=bfs(1);

rear:=bfs(head);

m:=0;

dfs(rear,head);

inc(m);

l[m]:=head;

min:=maxlongint;

for i:=1 to m do begin

fillchar(d,sizeof(d),0);

fillchar(v,sizeof(v),true);

fillchar(q,sizeof(q),0);

t:=0;

for j:=i to m do

if t+a[l[j],l[j+1]]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

编译不通过...

├ 测试数据 01：答案正确... 1000000000000ms

├ 测试数据 02：答案不正确... 0ms

├ 测试数据 03：答案不正确... 0ms

├ 测试数据 04：答案不正确... 0ms

├ 测试数据 05：答案不正确... 0ms

├ 测试数据 06：答案不正确... 0ms

├ 测试数据 07：答案不正确... 0ms

├ 测试数据 08：答案不正确... 41ms

├ 测试数据 09：答案不正确... 41ms

├ 测试数据 10：答案不正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：10 有效耗时：82ms

为啥？？？

60行AC...

险过...

O（n接近4）的算法

floyed加暴力枚举，管它什么直径不直径的，

枚举两个点

枚举两个点的路径的点

枚举另外的点

求最大值

在更新最小值

AC...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

心都碎了！！

小错误不断，害我一直提交啊不通过……

尤其是

（找到直径后用数组记录下来，然后在直径上枚举核的时候，

很容易把节点自身的编号和节点在数组中下标给搞混了！！！！）

同志们要当心啊，题目难度不大

可是要细心 细心 再细心！！！变量多了，很容易搞混！！！

至于算法和解题思路，下面很多大牛提出来了 小的就不献丑了…………

我也是看了才知道怎么做的……

Accepted 有效得分：100 有效耗时：97ms

超级弱智的O(n^3)的方法，哪位大牛能指教一下O(n)的算法啊，不胜感激T^T

ORZ LS 传说哥 犀利

牛B 居然0M

Accepted 有效得分：100 有效耗时：0ms

本来可以1A的...但是输出答案是犯了点低级错误...居然也有70...

这些数据中与路径P距离最长的节点。竟然有8个点在树的一条最长路径上（不知道是不是我的RP比较好）

===========---|---|-===============

n次BFS,求出 树中任意两点间的距离O(n^2);

然后很容易找到树网的中点...

当中点在一条边a-b中间时

1>如果该边>s,则路径P为该边距中点最近的那个顶点.

2>如果该边d[kb],则扩展kb(kb为s2的子节点),将kb加入P,s2:=kb;(扩展的前提是路径长度不超过限制);(很容易证明的贪心)

复杂度为O(n);

求出P后,再输出答案即可(很容易得出答案,不过我还是在这里出了点小错误.囧...)

总时间复杂度O(n^2).

Code:

program voj1362;

var i,j,k,n,lim,x,y,s1,s2,tot:longint;

z,max,now,ans:double;

p:array[0..300,0..300]of longint;

t,s,pre,path,ll,rr,dd:array[0..300]of longint;

ms,m0:array[0..300]of double;

f:array[0..300,0..300]of double;

b:array[0..300]of boolean;

procedure bfs(v:longint);

var i,j,k,l,r,x,y:longint;

begin

fillchar(b,sizeof(b),true);

for i:=1 to t[v] do begin

s[i]:=p[v,i];

b[s[i]]:=false;

pre[s[i]]:=v;

end; b[v]:=false;

l:=1; r:=t[v]; k:=r;

repeat

for i:=l to r do

for j:=1 to t[s[i]] do

if b[p[s[i],j]] then begin

x:=s[i]; y:=p[x,j];

f[v,y]:=f[v,x]+f[x,y];

inc(k); s[k]:=y; b[y]:=false;

pre[y]:=x;

end;

l:=r+1; r:=k;

until l>r;

//==========================================

for i:=1 to n do

if f[v,i]>max then begin

max:=f[v,i]; s1:=v; s2:=i;

path:=pre;

end;

end;

procedure dfs(v:longint);

var i:longint;

begin

ll[v]:=tot; b[v]:=false;

s[tot]:=v;

for i:=1 to t[v] do

if b[p[v,i]] then begin

inc(tot); dfs(p[v,i]);

end;

rr[v]:=tot;

end;

begin

readln(n,lim);

for i:=1 to n-1 do begin

readln(x,y,z);

inc(t[x]); p[x,t[x]]:=y;

inc(t[y]); p[y,t[y]]:=x;

f[x,y]:=z; f[y,x]:=z;

end;

for i:=1 to n do bfs(i);

//=============find中心=====================

i:=s2;

repeat

if f[path[i],s2]>=max/2 then break;

i:=path[i];

until i=s1;

f[0,path[i]]:=f[path[i],s2]-max/2;

f[0,i]:=f[path[i],i]-f[0,path[i]];

if f[path[i],i]>lim then begin//如果该边>lim,则路径P为该边距中点最近的那个顶点.

if f[0,path[i]]max then max:=f;

writeln(max:0:0);

halt;

end;

//==========================================

s1:=i; s2:=path[i];

fillchar(b,sizeof(b),true);

tot:=1; b[s2]:=false; dfs(s1);

inc(tot); b[s2]:=true; dfs(s2);//生成前序遍历

for i:=1 to n do

for j:=ll[i]+1 to rr[i] do

if f[i,s[j]]>ms[i] then ms[i]:=f[i,s[j]];

//==========================================

fillchar(b,sizeof(b),true); b[s1]:=false; b[s2]:=false;

now:=f[s1,s2];

repeat//求路径P

k:=s1;

if ms[s2]>ms[s1] then k:=s2;

z:=0; j:=-1;

for i:=1 to t[k] do

if (f[k,p[k,i]]+ms[p[k,i]]>z) and (now+f[k,p[k,i]]lim;

z:=0;

for i:=1 to n do

if not b[i] then

for j:=1 to t[i] do

if b[p] and (f[i,p]+ms[p]>z) then

z:=f[i,p]+ms[p];

writeln(z:0:0);

end.

106行,貌似写得有点长了...

完全floyed强过

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 88ms

├ 测试数据 08：答案正确... 212ms

├ 测试数据 09：答案正确... 541ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：841ms

SUNNY好慢！！

明明应该是运行时错误 VJ评测机也能出结果！！太误导人了！！

事实证明DFS＋Floyd是可以过的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：66ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 0ms

O(n^2)的算法，BFS+枚举=AC

program core;

var

a,long,f,ff,L:array[1..300,1..300] of longint;

len,b,llen,it,bb,f3:array[1..300] of longint;

h:array[1..300,1..2] of longint;

i,j,k,n,ss,m,s,t,x,y,z,tt,big,st,en,itslong,longnum,ans:longint;

gg,g:array[1..300] of boolean;

w:boolean;

begin

readln(n,ss);

fillchar(len,sizeof(len),0);

for k:=1 to n-1 do

begin;

readln(i,j,a);

a[j,i]:=a;

inc(len[i]);

long:=j;

inc(len[j]);

long[j,len[j]]:=i;

end;

m:=1;

for i:=1 to n do

if len[i]= 1 then

begin

b[m]:=i;

bb[i]:=m;

inc(m);

gg[i]:=true;

end;

dec(m);

fillchar(ff,sizeof(ff),0);

fillchar(f,sizeof(f),0);

for i:=1 to m do

begin

fillchar(g,sizeof(g),false);

s:=1;

t:=2;

h[1,1]:=b[i];

h[1,2]:=0;

g[b[i]]:=true;

f[b[i],i]:=b[i];

ff[b[i],i]:=0;

while s

天阿。。。

我写了个暴力到极点的O（N^4）算法。。

居然AC了。。。

不得不说这是NOIP2007中最简单的一道了。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

O(n^2) BFS 每个点 记录长度和路径 然后再枚举核即可

只用DFS...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 103ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：103ms

果然就是求一条直径即可。

但官方的数据没有第像九个点那么强的。