比赛 不平凡的世界 评测结果 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.