#15为何RTE?难道是栈溢出?

RT。可能是极限数据,最大生成树是一条链?
我初始化写的DFS可能爆栈,改用BFS能过吗?

4 条评论

  • @ 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*吗?

    • @ 2014-10-06 16:56:41

      是LCA啊,我用了搜索预处理树上的倍增啊。

      话说RTE的原因查出来了:std::sort的第三个参数cmp函数中,比较时必须使用<或>而非<=或>=。

  • 1

信息

ID
1843
难度
7
分类
(无)
标签
递交数
5319
已通过
954
通过率
18%
被复制
10
上传者