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!!!

此题难点：

（1）题难看懂。。。

（2）如何存边

由于边不多，我推荐用边表，记录每条路的第二个点，最后一个点，长度（其实为了建表方便最好连倒二的点也记下）

接下来用水搜就能AC了

（写一小时，一次AC，爽啊！！！）

为什么我好慢。