我的想法是暴力的把所有找到的直径都存起来，结果第9个点明显的MEMORY OVERFLOW。

结果还是……

这个题AC不易，不过如果在考场上调试好的话可以明显的过9个点还是很值（前提是你的手速要快）

program core;

type rec=record

ns,len:longint;

node:array [1..301] of integer;

end;

var

table:array [1..301,1..301] of record

s:integer;

long:longint;

end;

ogdata:array [0..301,0..301] of longint;

next:array [1..301] of integer;

use:array [1..301] of boolean;

d:array [1..300] of rec;

path:rec;

a,b,tmp,i,j,k,l,over,min,ans,flen,dlen,now,n,s:longint;

procedure getd(l:longint;step:integer);

var

i,j:integer;

flag,f:boolean;

begin

if flen=1 then begin

if l>dlen then dlen:=l;

end

else if l=dlen then begin

flag:=false;

for i:=1 to now do if step=d[i].ns then begin

f:=true;

for j:=step downto 1 do if d[i].node[j]path.node[step-j+1] then begin

f:=false;

break;

end;

if f then begin

flag:=true;

break;

end;

end;

if flag=false then begin

inc(now);

d[now]:=path;

d[now].ns:=step;

end;

end;

end;

procedure find(step,root:integer;l:longint);

var

flag:boolean;

i:integer;

begin

path.node[step]:=root;

path.len:=l;

use[root]:=true;

flag:=false;

for i:=1 to next[root] do if use[table[root,i].s]=false then begin

find(step+1,table[root,i].s,l+table[root,i].long);

flag:=true;

end;

if flag=false then getd(l,step);

use[root]:=false;

path.len:=path.len-l;

path.node[step]:=0;

end;

procedure ecc(root:integer;l:longint);

var

flag:boolean;

i:integer;

begin

use[root]:=true;flag:=false;

for i:=1 to next[root] do if use[table[root,i].s]=false then begin

ecc(table[root,i].s,l+table[root,i].long);

flag:=true;

end;

if flag=false then if l>ans then ans:=l;

use[root]:=false;

end;

begin

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

fillchar (next,sizeof(next),0);

fillchar (table,sizeof(table),0);

fillchar (ogdata,sizeof(ogdata),0);

for i:=0 to 300 do begin

ogdata[0,i]:=maxlongint-1;

ogdata:=maxlongint-1;

end;

assign (input,'core.in');

reset (input);

readln (n,s);

for i:=1 to n-1 do begin

readln (a,b,tmp);

inc(next[a]);table[a,next[a]].s:=b;table[a,next[a]].long:=tmp;

inc(next);table[b,next].s:=a;table[b,next].long:=tmp;

ogdata[a,b]:=tmp;

ogdata:=tmp;

end;

close (input);

assign (output,'core.out');

rewrite (output);

now:=0;dlen:=0;

fillchar (use,sizeof(use),0);

for flen:=1 to 2 do begin

for i:=1 to n do begin

fillchar (path,sizeof(path),0);

find(1,i,0);

end;

end;

min:=maxlongint;

for i:=1 to now do begin

k:=s;l:=d[i].ns;

if s>=dlen then l:=1 else begin

while k>=0 do begin

k:=k-ogdata[d[i].node[l],d[i].node[l-1]];

dec(l);

end;

inc(l);

end;

for j:=1 to l do begin

fillchar (use,sizeof(use),0);

k:=s;over:=j;tmp:=0;

while k>=0 do begin

k:=k-ogdata[d[i].node[over],d[i].node[over+1]];

inc(over);

end;

dec(over);

for k:=j to over do use[d[i].node[k]]:=true;

for k:=j to over do begin

ans:=0;

ecc(d[i].node[k],0);

if ans>tmp then tmp:=ans;

use[d[i].node[k]]:=true;

end;

if tmp

1.FLOYD求出直径的端点

2.DFS找直径

3.用树型DP求出直径上每个点的子树的最长路径

4.用双指针枚举直径上的区间,求出区间的最小偏心距

复杂度为 O(n^3)

PS:

可以证明,不用枚举所有直径,

任何直径都可以求出答案

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

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

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

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

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

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

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

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

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

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

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

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

O(n^3)加一个最优化剪枝。全部0MS。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

orz tobright 大牛

第九个点只要 加一个最优性优化 就可以了

if ans=min_path then exit;

暴力算法就可以了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

全部算法我都贴出来了，如果觉得好顶一下，谢谢。

PS：这是带文件输入输出的，要是想拿这个A题。得改一改...

O(n3)

program core;

const mn=5000;

var intree:array[1..mn] of boolean;

mid,map,ecc,dist:array[1..mn,1..mn] of longint;

w,t1,t2,a,s,b,c,k,max,t,i,j,n:longint;

procedure inst(a,b:longint);

begin

if (intree[a])and(intree) then exit;

if mid[a]0 then begin

inst(a,mid[a]);

inst(mid[a],b);

end;

intree[a]:=true;

intree:=true;

end;

function calc(i,j:longint):longint;

begin

if dist[i][j]>=0 then exit(dist[i][j]);

if i=j then dist[i][j]:=map[w][i] else begin

if mid[i][j]0 then begin

t1:=calc(i,mid[i][j]);

t2:=calc(mid[i][j],j);

if t1map[w][i] then dist[i][j]:=map[w][i];

if dist[i][j]>map[w][j] then dist[i][j]:=map[w][j];

end;

dist[j][i]:=dist[i][j];

calc:=dist[i][j];

end;

begin

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

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

readln(n,s);

for i:=1 to n do

for j:=1 to n do

map:=maxlongint shr 3;

for i:=1 to n do

map[i][i]:=0;

for i:=1 to n-1 do begin

readln(a,b,c);

map[a,b]:=c;

map:=c;

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if map[i][k]+map[k][j]max then max:=map[i][j];

fillchar(intree,sizeof(intree),false);

for i:=1 to n do

for j:=i+1 to n do if map[i][j]=max then

inst(i,j);

fillchar(ecc,sizeof(ecc),0);

for w:=1 to n do begin

for i:=1 to n do

for j:=1 to n do

dist[i][j]:=-1;

for i:=1 to n do if intree[i] then

for j:=i to n do if intree[j] then if map[i][j]ecc[i][j] then ecc[i][j]:=t;

end;

end;

max:=maxlongint;

for i:=1 to n do

for j:=i to n do

if (intree[i])and(intree[j])and(map[i][j]max then begin

max:=map[i][j];

a:=i; b:=j;

end;

end;

e:=0;

fillchar(vis,sizeof(vis),false);

repeat

inc(e);

vis[a]:=true;

list[e]:=a;

for i:=1 to n do

if leng[a][i]+map[sl[a][i]]=map[a] then begin

a:=sl[a][i];

break;

end;

until a=b;

if list[e]b then begin

inc(e); list[e]:=b;

vis:=true;

end;

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

for i:=1 to e do

c:=getmax(list[i]);

min:=maxlongint;

for a:=1 to e do begin

w:=map[list[1]][list[a]];

for b:=a to e do begin

if map[list[a]][list]>s then break;

if f[list]>w then w:=f[list];

y:=map[list[e]][list];

if w>y then begin if wt then min:=t; end;

end;

writeln(min);

end.

楼下应该是所有算法的代码都在这...

水题

随便找一点v1，然后找离他最远的点v2。

再用找到的那个点v2，找离它最远的点v3。

第二次找到的就是直径的两个端点v2,v3。

求树两点间的距离和路径O(n^2)就行了，用floyd慢

恩...努力了1天 第九个点终于过了 虽然没秒杀 - -！

最朴素的floyd+枚举核 一共500+ms 大牛们见笑了~~~

话说第九个点...真是...

const maxn=300000;mm=300;

var i,j,k,l,top,n,s,a,b,len,st,en,max,maxd,ecc:longint;

p:array[1..mm,1..mm]of integer;

f:array[1..mm,1..mm]of longint;

d:array[1..mm]of longint;

ab:array[1..mm]of integer;

path:array[1..90000,1..2]of integer;

procedure floyd;

begin

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (ij)and(ik)and(jk) then

if f>f+f[k,j] then

begin

f:=f+f[k,j];

p:=p[k,j];

end;

end;

begin

readln(n,s);

for i:=1 to n do

for j:=1 to n do

if i=j then f:=0 else f:=maxn;

for i:=1 to n-1 do

begin

read(a,b);

readln(f[a,b]);

f:=f[a,b];

p[a,b]:=a;

p:=b;

end;

floyd;

maxd:=0;top:=0;

for i:=1 to n-1 do

for j:=i+1 to n do

if (f>maxd)and(fmaxn) then maxd:=f;

for i:=1 to n-1 do

for j:=i+1 to n do

if f=maxd then begin inc(top);

path[top,1]:=i;

path[top,2]:=j;

end;

ecc:=maxn;

for l:=1 to top do

begin

len:=0;st:=path[l,1];en:=path[l,2];

k:=en;

while kst do

begin

inc(len);

ab[len]:=k;

k:=p[st,k];

end;

for i:=1 to len do

begin

st:=ab[i];max:=-1;

for k:=1 to n do d[k]:=f[k,st];

for k:=1 to n do if d[k]>max then max:=d[k];

if max=-1 then max:=maxn;

if ecc>max then ecc:=max;

for j:=i+1 to len do

begin

en:=ab[j];max:=-1;

if f[st,en]>s then break;

for k:=1 to n do

if d[k]>f[k,en]then d[k]:=f[k,en];

for k:=1 to n do

if d[k]>max then max:=d[k];

if max=-1 then max:=maxn;

if ecc>max then ecc:=max;

end;

end;

end;

writeln(ecc);

end.

自从NOIP2007之后见到这道题开始学OI

直到现在才AC....

这道题有O(n)算法，并且是个很简单的算法……

提示：2次BFS找直径、简单树形DP和单调队列……

加强版还得靠o(n)算法

没ＯＭＳＡＣ真的是心有不甘

谁让我用了ＦＬＯＥＹＤ求点距呢

３００*３００*３００＝２７００００００那还玩毛啊

小心第９个极端数据，３００个点以分布在１为圆心的圆上，直径有２９９*２９８条

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

100行=100分

大牛都0ms 小菜只是枚举O(n^3+)

去年的题，没看懂- -| 没想到只是Floyed+模拟。。。

囧。。。

编译通过...

├ 测试数据 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)果然秒了。。。

单调队列不会用。。/_\

定理：从树中的任意一点a出发找到离它最远的一点b，再从b出发找到离b最远的一点c，则bc是一条直径。。

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

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

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

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

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

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

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

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

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

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

o(n^3)也这么快···

{

引理：如果树有多条直径，则每条直径上都存在一个core。

证明：首先，如图，如果ABCD和FBCE都是直径的话，则AB=FB，CD=CE（如果不然，可设AB>FB，则FBCEAG，ecc=max{BF,ID}。也就是说，如果路径和公共段有交集，实际计算max时，只需要计算路径在公共段上的部分的ecc，然后和公共段两端的路径长取一遍MAX就行了。

下面证明，使得ecc取到最小的core必然和公共段有交集。设没有交集，则必然有一条直径和这个core没有交集，此core的ecc就至少严格大于公共段长度+除去公共段的半条路径长度，然而，公共段上的点到其他点的最长距离，最大不会大于这个长度，这与ecc最小矛盾！

通过上面的论述，得出core只与公共段有关，也就是说引理成立。所以在计算时任选一条直径即可，}

永远不希望再看到的题目

我写了183行！

O(n)；

0 ms;

第222个通过。

树形DP+数学论证+小范围枚举核

庆祝一下，500次提交，138题AC!!!