poj3249

显然是一道最短路径的题目,但是

1 ≤ n ≤ 100000, 0 ≤ m ≤ 1000000能轻松打爆dij+heap

怎么办?

挖掘题意,这是一个DAG图(有向无环图)

所以对于此类问题,我们有特殊的作法

对于DAG,拓扑序列在前的点的最短路一定会被先更新(值得思考)

所以我们只用对DAG做一次拓扑,然后依次更新最短路即可;(其实很像dp)

多个入度为0的点不影响结果;

再回到这题,由于给出的是点的权值

可以考虑拆点,将点i拆成点i1,i2,i1,i2之间连一条指向i2的有向边,权值为原先点的权值

原先所有入边连向i1,出边连i2,权值都是0,这样就搞定了

拆点的做法在后面的网络流中会经常用到(当然这题也可以不拆)

 type link=^node;
     node=record
       po,len:longint;
       next:link;
     end; var w:array[..] of link;
    v:array[..] of boolean;
    c,r,q,d:array[..] of longint;
    n,m,ans,i,t,f,s,x,y:longint;
    p,g:link;
function max(a,b:longint):longint;
  begin
    if a>b then exit(a) else exit(b);
  end; procedure add(x,y,z:longint);  //邻接表
  var p:link;
  begin
    new(p);
    p^.po:=y;
    p^.len:=z;
    p^.next:=w[x];
    w[x]:=p;
  end; begin
  while not eoln do
  begin
    readln(n,m);
    for i:= to *n do
      w[i]:=nil;
    fillchar(r,sizeof(r),);
    fillchar(c,sizeof(c),);
    for i:= to n do  //拆点
    begin
      readln(x);
      add(i+n,i,x);
      inc(r[i]);
      inc(c[i+n]);
    end;
    for i:= to m do  //建边
    begin
      readln(x,y);
      add(x,y+n,);
      inc(r[y+n]);
      inc(c[x]);
    end;
    s:=;
    fillchar(v,sizeof(v),false);
    fillchar(q,sizeof(q),);
    for i:= to *n do   //先找入度为0的点
      if r[i]= then
      begin
        inc(s);
        v[i]:=true;
        q[s]:=i;
      end;
    f:=;
    while s<*n do      //生成拓扑序列
    begin
      inc(f);
      p:=w[q[f]];
      while p<>nil do
      begin
        dec(r[p^.po]);
        if r[p^.po]= then
        begin
          inc(s);
          q[s]:=p^.po;
        end;
        p:=p^.next;
      end;
    end;
    for i:= to *n do     //d[i]表示从某个入度为0的点到达当前点的最大距离
      if v[i] then d[i]:= else d[i]:=-;
    ans:=-;
    for i:= to *n do
    begin
      f:=q[i];
      p:=w[f];
      g:=nil;
      while p<>nil do   //按照拓扑序列依次更新所有到达的点
      begin
        t:=p^.po;
        d[p^.po]:=max(d[p^.po],d[f]+p^.len);
        g:=p;
        p:=p^.next;
        dispose(g);   //注意这题多测加上巨大的n,m很有可能把链表挤爆,所以及时释放掉空间
      end;
    end;
    for i:= to *n do
      if c[i]= then ans:=max(d[i],ans);
    writeln(ans);
  end;
end.

拓扑序列复杂度O(m),最短路O(m)

所以总的复杂度O(m)

上一篇:洛谷P2336 喵星球上的点名


下一篇:spring MVC 使用 hibernate validator验证框架,国际化配置