/ Vijos / 讨论 / 问答 /

求治~~2014联合权值

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 条评论

  • @ 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