NOT A BLOG | sqybi

NOI 2006 — 最大获利(profit)

Posted on 四月 7th, 2008.

很经典的一道网络流的题目了.

话说今天很神奇啊,突然就把网络流学会了,还写了两道题都没出错.
极力推荐Dinic,又短又好写速度还巨快(不要扯时间复杂度,Dinic的实际速度比预计的快不是一点).
原来HopCroft就是简化版的Dinic啊…

这道题需要把每个用户群看做一个结点,每个中转站看做一个结点.
然后源连到用户群权值是用户群的获益,用户群连到中转站权值正无穷,中转站连到汇权值中转站花费.

因为最大获益=用户总获益-未选择用户群应得获益-中转站花费=用户总获益-(未选择用户群应得获益+中转站花费)
而对于这个网络流模型,它的最小切割的意义就是未选择用户群应得获益+中转站花费.
这样,只要求出最小切割,然后用用户总获益减去最小切割就可以了.
根据神奇的最小切割最大流定理,求一个最大流,问题解决.

显然我用了Dinic,速度巨爽无比.
远远把DFS多路增广甩在了后面(废话…Dinic有分层图思想…).

另:这道题用FPC编译(似乎是老版本),即使除去inline,也会RE掉,不知道为什么.Delphi正常.

还有,我已经无法忍受WP自动将英文标点转成中文,于是找Thity要了些空间.过段时间开通.
到时候自己改一下WP的源码.

附程序.

{
NOI 2006; 最大获利; profit
- sqybi’s code
- 最小切割最大流
- Dinic
}
//for my winsty
program profit_sqybi;
  const
    fin = ‘profit.in’;
    fout = ‘profit.out’;
    nn = 5000;
    mm = 50000;
    tt = nn + mm + 2;
    ee = mm * 3 + nn;

  var
    n, m, i, s, t, r, x, y, z, edgeNum: longint;
    adj, next, c, f: array[-ee..ee]of longint;
    head, dist, place: array[1..tt]of longint;
  function min(x, y: longint): longint; inline;
    begin
      if x < y then
        min := x
      else
        min := y;
    end;

  procedure addEdge(x, y, z: longint); inline;
    begin
      inc(edgeNum);
      adj[edgeNum] := y;
      next[edgeNum] := head[x];
      head[x] := edgeNum;
      c[edgeNum] := z;
      f[edgeNum] := 0;
      adj[-edgeNum] := x;
      next[-edgeNum] := head[y];
      head[y] := -edgeNum;
      c[-edgeNum] := 0;
      f[-edgeNum] := 0;
    end;

  function bfs: boolean; inline;
    var
      now, temp, qs, qe: longint;
      q: array[1..tt]of longint;
      v: array[1..tt]of boolean;
    begin
      fillchar(dist, sizeof(dist), 0);
      qs := 1;
      qe := 1;
      q[1] := s;
      fillchar(v, sizeof(v), false);
      v[1] := true;
      while qs <= qe do begin
        now := q[qs];
        temp := head[now];
        while temp <> 0 do begin
          if (not v[adj[temp]]) and (f[temp] < c[temp]) then begin
            v[adj[temp]] := true;
            inc(qe);
            q[qe] := adj[temp];
            dist[adj[temp]] := dist[now] + 1;
          end;
          temp := next[temp];
        end;
        inc(qs);
      end;
      bfs := dist[t] <> 0;
    end;

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

  begin
    assign(input, fin);
    assign(output, fout);
    reset(input);
    rewrite(output);

    readln(n, m);
    s := 1;
    t := m + n + 2;
    for i:=1 to n do begin
      read(x);
      addEdge(m+1+i, t, x);
    end;
    readln;
    r := 0;
    for i:=1 to m do begin
      readln(x, y, z);
      r := r + z;
      addEdge(s, i+1, z);
      addEdge(i+1, m+1+x, maxlongint);
      addEdge(i+1, m+1+y, maxlongint);
    end;

    while bfs do begin
      place := head;
      r := r - dfs(s, maxlongint);
    end;

    writeln(r);

    close(input);
    close(output);
  end.

阅读(379 次)

Make a Comment

Make A Comment: ( 5 so far )

5 Responses to “NOI 2006 — 最大获利(profit)”

Comments RSS Feed

Where's The Comment Form?