NOT A BLOG | sqybi

SPOJ 371 — Boxes (code: BOXES)

Posted on 五月 17th, 2008.

一道很经典的费用流题目,也是第一次写费用流.SPFA写错了一点.另外终于理解上次SGU那道题为啥可以用费用流了…

题目描述懒得写了…
建图的方法:
s到每个盒子连边,容量为盒子里球的数量,费用0.
盒子到t连边,容量为1,费用0.
相邻的两个盒子连边,容量为正无穷,费用1.
要求的就是最小费用.

{
SPOJ 371; BOXES
- sqybi’s code
- 最小费用最大流
}
//for my winsty
program boxes_sqybi;
  const
    nn = 1000;
    inf = 100000000;
    mm = nn * 4;
    tt = nn + 2;

  var
    cases, times, n, m, s, t, i, x, y, qs, ql, temp, now, res: longint;
    head, dist, go, path, pathEdge: array[1..tt]of longint;
    q: array[0..tt-1]of longint;
    flag: array[1..tt]of boolean;
    flow, next, adj, w, capa: array[-mm..mm]of longint;

  procedure addEdge(x, y, c, z: longint);
    begin
      inc(m);
      adj[m] := y;
      capa[m] := c;
      w[m] := z;
      flow[m] := 0;
      next[m] := head[x];
      head[x] := m;
      adj[-m] := x;
      capa[-m] := 0;
      w[-m] := -z;
      flow[-m] := 0;
      next[-m] := head[y];
      head[y] := -m;
    end;

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

  begin
    readln(cases);
    for times:=1 to cases do begin
      readln(n);
      s := 1;
      t := n + 2;
      m := 0;
      fillchar(head, sizeof(head), 0);
      for i:=2 to n+1 do begin
        read(x);
        addEdge(s, i, x, 0);
        y := i - 1;
        if y = 1 then y := n + 1;
        addEdge(i, y, inf, 1);
        y := i + 1;
        if y = n + 2 then y := 2;
        addEdge(i, y, inf, 1);
        addEdge(i, t, 1, 0);
      end;
      readln;
      repeat
        for i:=s+1 to t do dist[i] := inf;
        dist[s] := 0;
        fillchar(go, sizeof(go), 0);
        go[s] := inf;
        qs := 0;
        ql := 1;
        q[0] := s;
        fillchar(flag, sizeof(flag), true);
        flag[s] := false;
        while ql <> 0 do begin
          now := q[qs];
          temp := head[now];
          while temp <> 0 do begin
            if (flow[temp] < capa[temp]) and (dist[now] + w[temp] < dist[adj[temp]]) then begin
              dist[adj[temp]] := dist[now] + w[temp];
              go[adj[temp]] := min(go[now], capa[temp]-flow[temp]);
              path[adj[temp]] := now;
              pathEdge[adj[temp]] := temp;
              inc(ql);
              q[(qs+ql-1) mod t] := adj[temp];
              flag[adj[temp]] := false;
            end;
            temp := next[temp];
          end;
          flag[now] := true;
          qs := (qs + 1) mod t;
          dec(ql);
        end;
        if dist[t] = inf then break;
        now := t;
        while now <> s do begin
          flow[pathEdge[now]] := flow[pathEdge[now]] + go[t];
          flow[-pathEdge[now]] := - flow[pathEdge[now]];
          now := path[now];
        end;
      until false;
      res := 0;
      for i:=1 to m do
        res := res + flow[i] * w[i];
      writeln(res);
    end;
  end.

阅读(135 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “SPOJ 371 — Boxes (code: BOXES)”

Comments RSS Feed

Where's The Comment Form?