72 条题解
-
0
eiwoqu LV 5 @ 2008-10-07 14:19:00
向大牛们咨询一个问题：这道题怎么就不存在有一个点是有2个入度呢？
我都服了，比赛的时候本来向用朴素写一个，但是考虑到有可能有这种情况，所以就直接写了一个FLOYD，结果过了2个。-
swm @ 2015-07-03 20:30:17
树结构不会的吧
-
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 134ms
├ 测试数据 07：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 08：答案正确... 462ms
├ 测试数据 09：答案正确... 509ms
├ 测试数据 10：运行时错误...| 错误号: 202 | 堆栈溢出错var
z:int64;
h,v,g:array[1..20004]of int64;
s:array[1..20004,1..3]of int64;
a,b,c,n,m,i,j,t,q:longint;
procedure dfs(l1,l2:longint);
var
k,i,l3:longint;
begin
k:=l1;
i:=0;
repeat
{while u -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
不用非递归也能全0ms啊。数组模拟链表+dfs，结束时间戳f的等号不能掉啊，害的我一直wa，还有结果和距离要用int64。 -
0
Sunstrider LV 3 @ 2008-10-05 20:26:53
var
n,i,u,v:0..10000;
m,j:0..100000;
fathers:array[0..10000]of 0..10000;
times:array[0..10000]of dword;
time,father,sum,sumtime:int64;
could:boolean;
begin
readln(n,m);
for i:=1 to n-1 do
begin
read(time,father);
fathers[father]:=time;
readln(time);
times[father]:=time
end;sumtime:=0;
sum:=0;
for j:=1 to m do
begin
readln(u,v);
father:=v;
time:=0;
could:=true;
while (fatheru) do
begin
time:=time+times[father];
father:=fathers[father];
if (father=1) and(u1) then begin could:=false; break end;
end;
if could then begin sum:=sum+1; sumtime:=sumtime+time end;
end;
writeln(sum);
writeln(sumtime);
end.有谁帮我看看。
思路：记录每个节点的父节点（fathers）和到父节点的时间（times）；
从最低点（v）搜索，如果最高点是它的父节点（u），那么，记录时间，退出；
如果搜到底（第一个点）还没有结果，就退出。
但有若干个点运行超时...
谁能帮我？ -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：运行时错误...| 错误号: 202 | 堆栈溢出错
怎么回事?
program rally;
type
link=^rec;
rec=record
w:longint;
next:link;
end;
var
a,b:array[1..10000]of link;
f,fa,c,d:array[0..10000]of longint;
root,n,m,i,k,u,vv,t,way:longint;
ans,sum:qword;
v:array[1..10000]of boolean;
p:link;
function find(x:longint):longint;
begin
if f[x]x then f[x]:=find(f[x]);
exit(f[x]);
end;
function dist(x,y:longint):qword;
begin
{writeln(x,' ',y);
writeln(d[x],' ',d[y]);}
dist:=d[x]-d[y];
end;
procedure search(x:longint);
var g,h:longint;
p:link;
begin
v[x]:=true; p:=b[x];
while pnil do
begin
if v[p^.w] then
begin
h:=find(p^.w);
if h=p^.w then
begin inc(sum); inc(ans,dist(x,p^.w)); end;
end;
p:=p^.next;
end;
f[x]:=x; p:=a[x];
while pnil do
begin
search(p^.w);
p:=p^.next;
end;
f[x]:=fa[x];
end;
procedure dfs(x:longint);
var p:link;
begin
p:=a[x];
while pnil do
begin
d[p^.w]:=d[x]+c[p^.w];
dfs(p^.w);
p:=p^.next;
end;
end;
begin
assign(input,'rally.in'); reset(input);
assign(output,'rally.out'); rewrite(output);
readln(n,m);
fillchar(v,sizeof(v),0);
for i:=1 to n-1 do
begin
readln(u,vv,t); v[vv]:=true;
fa[vv]:=u; c[vv]:=t;
new(p); p^.w:=vv;
p^.next:=a; a:=p;
end;
for i:=1 to n do
if not v[i] then
begin root:=i; break; end;
fillchar(v,sizeof(v),0);
for i:=1 to m do
begin
readln(u,vv);
new(p); p^.w:=u;
p^.next:=b[vv]; b[vv]:=p;
end;
ans:=0; sum:=0; way:=0; d[root]:=0;
dfs(root);
search(root);
writeln(sum); writeln(ans);
close(input); close(output);
end. -
0
TestTestTest LV 3 @ 2008-10-03 17:41:26
经测试每个点不超过15个儿子，开10000*15的邻接表可以AC，编程难度下降
DFS记时间戳···· -
0
tracy-henry LV 10 @ 2008-10-02 14:40:42
又是车
eiwoqu
LV 5
@ 2008-10-07 14:19:00
