- 货车运输
- 2014-10-06 14:42:53 @
RT。可能是极限数据,最大生成树是一条链?
我初始化写的DFS可能爆栈,改用BFS能过吗?
4 条评论
-
WolfCarb LV 8 @ 2014-11-20 21:58:43
发现少年= = 我也是....表示强行改成bfs还是RTE
-
2014-10-06 21:46:40@
==严格小于
如果a不大于b
b不大于a
a==b -
2014-10-06 21:40:29@
我tm刚做这题
70分求教
var
n,m,i,l,x,y,t,z,j:longint;
a:array[1..10000,1..10000]of longint;
fa,s:array[1..100000]of longint;
f,g:array[1..10000]of boolean;
function ceng(x:longint):longint;
begin
if fa[x]=x then exit(0);
exit(ceng(fa[x])+1);
end;
function lca(x,y:longint):longint;
begin
lca:=maxlongint;
while ceng(x)>ceng(y) do x:=fa[x]; while ceng(x)<ceng(y) do y:=fa[y];
while x<>y do
begin x:=fa[x];y:=fa[y];end;exit(x);
end;
procedure prim;
var
i,j,max,t:longint;
begin
for i:=2 to n do begin s[i]:=a[1,i];fa[i]:=1;end;
for i:=2 to n do
begin
max:=0;
for j:=1 to n do if (s[j]>max)and f[j]
then begin max:=s[j];t:=j;end;f[t]:=false;
for j:=2 to n do if f[j]and(j<>t)and(a[t,j]>s[j]) then begin s[j]:=a[t,j];fa[j]:=t;end;
end;
end;
begin
fillchar(f,sizeof(f),true);
f[1]:=false;fa[1]:=1;s[1]:=maxlongint;
read(n,m);
for i:=1 to m do
begin read(x,y,z);g[x]:=true;g[y]:=true;
if z>a[x,y] then a[x,y]:=z;if z>a[y,x] then a[y,x]:=z;end;
readln(l);
prim;
for i:=1 to l do begin read(x,y);if not g[x] or not g[y]then writeln(-1)
else begin
z:=lca(x,y);t:=maxlongint;
while x<>z do begin if a[x,fa[x]]<t then t:=a[x,fa[x]];x:=fa[x];end;
while y<>z do begin if a[y,fa[y]]<t then t:=a[y,fa[y]];y:=fa[y];end;
writeln(t);end;end;
end. -
2014-10-06 15:55:22@
这道题难道不是*lca*吗?
- 1
信息
- ID
- 1843
- 难度
- 7
- 分类
- (无)
- 标签
- 递交数
- 5319
- 已通过
- 954
- 通过率
- 18%
- 被复制
- 10
- 上传者