单调队列真好用

编译通过...

├ 测试数据 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

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

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

我的想法是暴力的把所有找到的直径都存起来，结果第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