比赛 |
不平凡的世界 |
评测结果 |
AAWAAAWWWW |
题目名称 |
不平凡的引线 |
最终得分 |
50 |
用户昵称 |
darkness |
运行时间 |
0.853 s |
代码语言 |
Pascal |
内存使用 |
3.79 MiB |
提交时间 |
2015-11-05 09:54:11 |
显示代码纯文本
type data=record
dot,t:longint;
end;
var m,u,n,len,i,tot,head,tail,mx,vv:longint;
ans:extended; pd,pd1:boolean;
ef,et,l,r,er:array[0..101000] of longint;
a,t,t1:array[0..101000] of longint;
v,vd:array[0..101000] of boolean;
q:array[0..101000] of data;
procedure add(x,y,len:longint);
var temp:longint;
begin
er[tot]:=x;
ef[tot]:=a[x];
a[x]:=tot;
et[tot]:=y;
l[tot]:=len;
inc(r[y]);
end;
function max(x,y:longint):longint;
begin
if (x>y) then exit(x);
exit(y);
end;
procedure init;
begin
fillchar(ef,sizeof(ef),0);
fillchar(et,sizeof(et),0);
fillchar(a,sizeof(a),0);
fillchar(t,sizeof(t),0);
fillchar(t1,sizeof(t1),0);
fillchar(v,sizeof(v),false);
fillchar(vd,sizeof(vd),false);
readln(m); pd:=true;
mx:=-100;
tot:=0;
for i:=1 to m do
begin inc(tot);
readln(u,vv,len);
if len<>1 then pd:=false;
add(u,vv,len);
inc(tot);
add(vv,u,len);
end;
fillchar(v,sizeof(v),false);
head:=0;tail:=0;
for i:=1 to (m+1) do
if (r[i]=1) then begin
inc(tail);q[tail].dot:=i;
q[tail].t:=0;v[i]:=true;end;
end;
procedure bfs;
var tt,ii,temp:longint;
begin
while (head<tail) do begin
inc(head);
tt:=a[q[head].dot];
while tt<>0 do begin
if (et[tt-1]=q[head].dot) then
temp:=tt-1 else temp:=tt+1;
if (not v[et[tt]]) then begin
v[et[tt]]:=true;t[et[tt]]:=q[head].t+1;
if (t[et[tt]])>mx then mx:=t[et[tt]];
inc(tail);q[tail].dot:=et[tt];
q[tail].t:=t[et[tt]];
vd[tt]:=true;vd[temp]:=true;
end;
tt:=ef[tt];
end;
end;
end;
procedure bfs1;
var tt,ii,temp:longint;
begin
while (head<tail) do begin
inc(head);
tt:=a[q[head].dot];
while tt<>0 do begin
if (et[tt-1]=q[head].dot) then
temp:=tt-1 else temp:=tt+1;
if (not v[et[tt]]) then begin
inc(t1[tt]); if (t1[tt]>=l[tt]) then begin
v[et[tt]]:=true;t[et[tt]]:=q[head].t+l[tt];
if (t[et[tt]])>mx then mx:=t[et[tt]];
inc(tail);q[tail].dot:=et[tt];
q[tail].t:=t[et[tt]];
vd[tt]:=true;vd[temp]:=true;
end;
end;
tt:=ef[tt];
end;
end;
end;
procedure work;
var j,k,kk,jj,o,now:longint;
cc:extended; ff:boolean;
begin
ff:=false; pd1:=true;
for j:=1 to tot do if (not vd[j]) then
begin now:=abs(t[er[j]]-t[et[j]]); vd[j]:=true;
l[j]:=l[j]-now; if (l[j]<=0) then continue
else begin jj:=max(t[er[j]],t[et[j]]);
cc:=l[j]/2;cc:=cc+jj;
if (not ff) then if(cc>mx) then begin ans:=cc;ff:=true;end;
if (ff) then if (cc>ans) then ans:=cc;
end;
end;
if (not ff) then pd1:=false;
end;
begin
assign(input,'firelead.in');
assign(output,'firelead.out');
reset(input);
rewrite(output);
init;
if (pd) then begin
bfs;writeln(mx,'.0');
end else begin bfs1;work;
if (not pd1) then writeln(mx,'.0') else
writeln(ans:0:1);
end;
close(input);
close(output);
end.