- 问答
- 2015-10-24 16:37:12 @
var a,b,c:array[1..200000] of longint;
t,s:array[1..1000000] of longint;
d:array[1..2000,1..2000] of boolean;
i,j,e,m,n,p,q,r:longint;
begin read(n);
for i:=1 to (n-1) do read(a[i] , b[i]);
for i:=1 to n do read(c[i]);
for i:=1 to (n-1) do d[a[i],b[i]]:=true;
q:=0; for i:=1 to n do
begin for j:=1 to n do
begin if d[i,j]= true then for m:=1 to n do
begin if d[j,m]= true then
begin inc(q); s[q]:=c[i]*c[m];writeln(s[q]);
end;
end;
end;
end;
r:=0;p:=0;e:=0;
for i:=1 to q do if s[i]>=p then P:=s[i];
for i:=1 to q do t[i]:=s[i] mod 10007 ;
for i:=1 to q do r:=r+s[i];
e:=2*r mod 10007;
write (p,' ',e);
readln;
end.
数据有问题,帮改改
5 条评论
-
LincHpin LV 8 @ 2015-10-31 08:53:16
首先注意题目中给的是无向边。
但是你在记录边的时候记录的是单向边,“ d[a[i],b[i]]:=true; ” 。
但是你下面扫描时只有当“d[i,j]= true” 且 “d[j,m]= true” 时才会记录。
这样的话如果一开始 d 数组中记录的是 d[i,j]=true d[m,j]= true
即有一条从i到j的边和一条从m到j的边。
此时( i , m ) 的距离为2,可以产生联合权值,但却不会被你的程序记录到答案中去
所以建议你在记录边时写成
“ d[a[i],b[i]]:=true;
d[b[i],a[i]]:=true; ”
(虽然这样做依旧会TLE) -
2015-10-30 21:41:29@
然而这道题只要推出正解公式,只要2个一维数组来个快排,图结构标签应该是链式前向星来存
-
2015-10-27 12:33:04@
= =
想过60%的数据??首先这题跟弗洛伊德一点关系都没有。
这个图实质是棵树。你按题目DFS走2步就能60分了。
存图去用前向星吧。
-
2015-10-26 15:06:07@
喜闻乐见弗洛伊德
-
2015-10-26 13:59:16@
我认为不会有人回的
- 1