NOT A BLOG | sqybi

SGU 185 — Two Shortest

Posted on 四月 8th, 2008.

经典的最短路+网络流的题目.

第一行n,m,表示n个点m条边.
接下来m行,每行描述一条无向边.x y z表示x,y之间一条无向边,长度为z.
要求求出两条没有公共边的最短路.

首先一个SPFA,目的是保留dist数组.
然后从最后一个结点开始BFS.对于BFS到某个结点x,如果结点y能够满足dist[y]+table[x, y]=dist[x],则将这条边作为y->x的有向边加入新图中,并将y加入BFS队列(如果y没有被加入过).
这样,新图中的边便都是能够构成最短路的边了.
接下来对于新图,每条边的容量都看作1,源是1,汇是n,做最大流.得出的最大流就是最短路条数.
如果条数少于2,输出无解.
如果大于等于2,那么这时我们会获得刚刚计算最大流时的flow数组.从源开始进行DFS,每次只走flow=1的结点,直到走到汇为止,把这条路径上所有flow都变成0.然后再走一次.得到的两条路径输出即可.

然后呢,我的网络流写的是Dinic.
于是,我的SPFA+Dinic就华丽的MLE掉了.

谁知道怎么优化内存…开链表不管用,链表会让内存更大.

Update:经过一晚上恶心死人的优化,终于AC了这道题.因为Delphi没有integer类型(Delphi的integer=fpc的longint…而我找不到相当于fpc的integer的类型),于是优化难了很多.最后用上了word,shortint和子界类型,终于AC掉.题目限制1MB内存,我用了1009KB,好险…
另外据Wind牛说,可以用最小费用流解.只要加一个源,流2的流量就行.
似乎Wind牛还有一个两遍SPFA的算法,未证明正确性.

{
SGU 185; Two shortest
- sqybi’s code
- 单源最短路 + 最大流
- SPFA + Dinic
}
//for my winsty
program sgu185_sqybi;
  const
    nn = 400;
    mm = nn * nn div 2;
    unable = nn * 10000 + 1;

  var
    n, m, i, qe, qs, r, edgeNum, x, y, z: longint;
    t: array[1..nn, 1..nn]of word;
    q: array[1..10*nn]of longint;
    dist, head, place, d: array[1..nn]of longint;
    f: array[1..nn]of boolean;
    adj: array[-mm..mm]of word;
    next: array[-mm..mm]of -400..400;
    flow, capa: array[-mm..mm]of shortint;

  function min(x, y: longint): longint;
    begin
      if x < y then
        min := x
      else
        min := y;
    end;

  procedure addEdge(x, y: longint);
    begin
      inc(edgeNum);
      adj[edgeNum] := y;
      next[edgeNum] := head[x];
      head[x] := edgeNum;
      flow[edgeNum] := 0;
      capa[edgeNum] := 1;
      adj[-edgeNum] := x;
      next[-edgeNum] := head[y];
      head[y] := -edgeNum;
      flow[-edgeNum] := 0;
      capa[-edgeNum] := 0;
    end;

  function bfs: boolean;
    var
      now, temp: longint;
    begin
      fillchar(dist, sizeof(dist), $FF);
      dist[1] := 0;
      qs := 1;
      qe := 1;
      q[1] := 1;
      while qs <= qe do begin
        now := q[qs];
        temp := head[now];
        while temp <> 0 do begin
          if (dist[adj[temp]] = -1) and (flow[temp] < capa[temp]) then begin
            dist[adj[temp]] := dist[now] + 1;
            inc(qe);
            q[qe] := adj[temp];
          end;
          temp := next[temp];
        end;
        inc(qs);
      end;
      bfs := dist[n] <> -1;
    end;

  function dfs(x, d: longint): longint;
    var
      delta, temp, r: longint;
    begin
      if x = n then begin
        dfs := d;
        exit;
      end;
      delta := 0;
      temp := place[x];
      while temp <> 0 do begin
        if (dist[adj[temp]] = dist[x] + 1) and (flow[temp] < capa[temp]) then begin
          r := dfs(adj[temp], min(capa[temp]-flow[temp], d-delta));
          flow[temp] := flow[temp] + r;
          flow[-temp] := -flow[temp];
          delta := delta + r;
          if delta = d then break;
        end;
        temp := next[temp];
      end;
      place[x] := temp;
      dfs := delta;
    end;

  procedure print(x: longint);
    var
      temp: longint;
    begin
      if x = n then exit;
      write(x, ‘ ‘);
      temp := head[x];
      while temp <> 0 do begin
        if flow[temp] = 1 then begin
          print(adj[temp]);
          flow[temp] := 0;
          break;
        end;
        temp := next[temp];
      end;
    end;

  begin
    readln(n, m);
    fillchar(t, sizeof(t), 0);
    for i:=1 to m do begin
      readln(x, y, z);
      t[x, y] := z;
      t[y, x] := z;
    end;

    //SPFA
    qs := 1;
    qe := 1;
    q[1] := 1;
    d[1] := 0;
    for i:=2 to n do
      d[i] := unable;
    fillchar(f, sizeof(f), false);
    f[1] := true;
    while qs <= qe do begin
      x := q[qs];
      for i:=1 to n do
        if t[x, i] <> 0 then
          if d[x] + t[x, i] < d[i] then begin
            d[i] := d[x] + t[x, i];
            if not f[i] then begin
              f[i] := true;
              inc(qe);
              q[qe] := i;
            end;
          end;
      f[x] := false;
      inc(qs);
    end;

    //create new graph
    qs := 1;
    qe := 1;
    q[1] := n;
    fillchar(f, sizeof(f), false);
    f[n] := true;
    while qs <= qe do begin
      x := q[qs];
      for i:=1 to n do
        if t[i, x] <> 0 then
          if d[i] + t[i, x] = d[x] then begin
            addEdge(i, x);
            if not f[i] then begin
              f[i] := true;
              inc(qe);
              q[qe] := i;
            end;
          end;
      inc(qs);
    end;

    //Dinic
    r := 0;
    while bfs do begin
      place := head;
      r := r + dfs(1, maxlongint);
    end;

    //output solution
    if r < 2 then
      writeln(’No solution’)
    else begin
      print(1);
      writeln(n);
      print(1);
      writeln(n);
    end;
  end.

阅读(257 次)

Make a Comment

Make A Comment: ( 6 so far )

6 Responses to “SGU 185 — Two Shortest”

Comments RSS Feed

Where's The Comment Form?