你好,欢迎来到中学生信息学竞赛网  

网站首页  |  收藏本站  |  报名热线:400-6967-311  |  官方QQ群:167322136

信息学竞赛QQ群
167322136
您当前所在位置:首页 > 辅导资料
辅导资料

费用流算法效率比较[转]

发布时间:2016-12-15 18:11:02
费用流算法效率比较[转]
 
编号:bellman
姓名:bellman
总分:100.0
 
第一题:napkin
用时:30.23s   得分:100.0
 
编号
结果
用时
空间
得分
0(napkin01.in)
正确
0.03s
6.99M
10.0
1(napkin02.in)
正确
0.05s
6.99M
10.0
2(napkin03.in)
正确
0.86s
6.99M
10.0
3(napkin04.in)
正确
1.09s
6.99M
10.0
4(napkin05.in)
正确
2.83s
6.99M
10.0
5(napkin06.in)
正确
3.25s
6.99M
10.0
6(napkin07.in)
正确
4.92s
6.99M
10.0
7(napkin08.in)
正确
13.91s
6.99M
10.0
8(napkin09.in)
正确
2.61s
6.99M
10.0
9(napkin10.in)
正确
0.69s
6.99M
10.0

 

编号:ff
姓名:ff
总分:100.0
 
第一题:napkin
用时:35.48s   得分:100.0
 
编号
结果
用时
空间
得分
0(napkin01.in)
正确
0.05s
5.86M
10.0
1(napkin02.in)
正确
0.03s
5.86M
10.0
2(napkin03.in)
正确
1.01s
5.86M
10.0
3(napkin04.in)
正确
1.23s
5.86M
10.0
4(napkin05.in)
正确
3.39s
5.86M
10.0
5(napkin06.in)
正确
3.78s
5.86M
10.0
6(napkin07.in)
正确
5.66s
5.86M
10.0
7(napkin08.in)
正确
16.73s
5.86M
10.0
8(napkin09.in)
正确
2.92s
5.86M
10.0
9(napkin10.in)
正确
0.67s
5.86M
10.0

 

编号:spfa
姓名:spfa
总分:100.0
 
第一题:napkin
用时:3.81s   得分:100.0
 
编号
结果
用时
空间
得分
0(napkin01.in)
正确
0.03s
7.24M
10.0
1(napkin02.in)
正确
0.05s
7.24M
10.0
2(napkin03.in)
正确
0.14s
7.24M
10.0
3(napkin04.in)
正确
0.20s
7.24M
10.0
4(napkin05.in)
正确
0.33s
7.24M
10.0
5(napkin06.in)
正确
0.58s
7.24M
10.0
6(napkin07.in)
正确
0.77s
7.24M
10.0
7(napkin08.in)
正确
0.69s
7.24M
10.0
8(napkin09.in)
正确
0.72s
7.24M
10.0
9(napkin10.in)
正确
0.31s
7.24M
10.0
 
 

spfa
program napkin;
type
  rec=record
    lim,cost,other,ed:longint;
  end;
const maxn=100000000;
var
  t:array[0..30000]of rec;
  next:array[0..30000]of longint;
  pre,best,first,now:array[0..2100]of longint;
  q:array[0..21000]of longint;
  ans,n,fa,fb,ff,tot,a,b:longint;
  
procedure insert(x,y,z,c:longint);
begin
  inc(tot);
  next[tot]:=first[x];first[x]:=tot;
  t[tot].ed:=y;t[tot].lim:=z;t[tot].cost:=c;t[tot].other:=tot+1;
  inc(tot);
  next[tot]:=first[y];first[y]:=tot;
  t[tot].ed:=x;t[tot].lim:=0;t[tot].cost:=-c;t[tot].other:=tot-1;
end;
procedure init;
var
  i,j,k,x,y:longint;
begin
  assign(input,'napkin.in');reset(input);
  assign(output,'napkin.out');rewrite(output);
  fillchar(first,sizeof(first),0);
  fillchar(next,sizeof(next),0);
  readln(n,a,b,ff,fa,fb);
  for i:=1 to n do begin
    read(k);
    insert(1,i+1,k,0);
    insert(i+1,n+n+2,maxn,ff);
    if i>1+a then insert(i+1,n+i-a,maxn,fa);
    if i>1+b then insert(i+1,n+i-b,maxn,fb);
    if i>1 then insert(i+1+n,i+n,maxn,0);
    insert(i+1+n,n+n+2,k,0);
  end;
  n:=n+n+2;
end;
procedure work;
var
  i,j,x,y,dx,cl,op:longint;
  flag:boolean;
begin
  ans:=0;
  while true do begin
    for i:=2 to n do best[i]:=maxn;best[1]:=0;
    fillchar(pre,sizeof(pre),0);pre[1]:=maxn;
    flag:=true;q[1]:=1; cl:=0;op:=1;
    while cl<op do begin
      inc(cl);i:=q[cl];
      x:=first[i];
      while x<>0 do begin
        y:=t[x].ed;
        if (t[x].lim>0)and(best[i]+t[x].cost<best[y]) then begin
          best[y]:=best[i]+t[x].cost;pre[y]:=i;now[y]:=x;
          inc(op);q[op]:=y;
        end;
        x:=next[x];
      end;
    end;
    if best[n]=maxn then break;
    
    i:=n;dx:=maxn;
    while i<>1 do begin
      j:=i;i:=pre[i];x:=now[j];
      if t[x].lim<dx then dx:=t[x].lim;
    end;
    
    i:=n;ans:=ans+best[n]*dx;
    while i<>1 do begin
      j:=i;i:=pre[i];x:=now[j];
      t[x].lim:=t[x].lim-dx;
      x:=t[x].other;t[x].lim:=t[x].lim+dx;
    end;
  end;
  writeln(ans);
  close(output);
end;
begin
  init;
  work;
end.
 


bellman
program napkin;
type
  rec=record
    lim,cost,other,ed:longint;
  end;
const maxn=100000000;
var
  t:array[0..30000]of rec;
  next:array[0..30000]of longint;
  pre,best,first,now:array[0..2100]of longint;
  ans,n,fa,fb,ff,tot,a,b:longint;
  
procedure insert(x,y,z,c:longint);
begin
  inc(tot);
  next[tot]:=first[x];first[x]:=tot;
  t[tot].ed:=y;t[tot].lim:=z;t[tot].cost:=c;t[tot].other:=tot+1;
  inc(tot);
  next[tot]:=first[y];first[y]:=tot;
  t[tot].ed:=x;t[tot].lim:=0;t[tot].cost:=-c;t[tot].other:=tot-1;
end;
procedure init;
var
  i,j,k,x,y:longint;
begin
  assign(input,'napkin.in');reset(input);
  assign(output,'napkin.out');rewrite(output);
  fillchar(first,sizeof(first),0);
  fillchar(next,sizeof(next),0);
  readln(n,a,b,ff,fa,fb);
  for i:=1 to n do begin
    read(k);
    insert(1,i+1,k,0);
    insert(i+1,n+n+2,maxn,ff);
    if i>1+a then insert(i+1,n+i-a,maxn,fa);
    if i>1+b then insert(i+1,n+i-b,maxn,fb);
    if i>1 then insert(i+1+n,i+n,maxn,0);
    insert(i+1+n,n+n+2,k,0);
  end;
  n:=n+n+2;
end;
procedure work;
var
  i,j,x,y,dx:longint;
  flag:boolean;
begin
  ans:=0;
  while true do begin
    for i:=2 to n do best[i]:=maxn;best[1]:=0;
    fillchar(pre,sizeof(pre),0);pre[1]:=maxn;
    flag:=true;
    while flag do begin
      flag:=false;
      for i:=1 to n do begin
        x:=first[i];
        while x<>0 do begin
          y:=t[x].ed;
          if (t[x].lim>0)and(best[i]+t[x].cost<best[y]) then begin
            best[y]:=t[x].cost+best[i];now[y]:=x;pre[y]:=i;flag:=true;
          end;
          x:=next[x];
        end;
      end;
    end;
    if best[n]=maxn then break;
    
    i:=n;dx:=maxn;
    while i<>1 do begin
      j:=i;i:=pre[i];x:=now[j];
      if t[x].lim<dx then dx:=t[x].lim;
    end;
    
    i:=n;ans:=ans+best[n]*dx;
    while i<>1 do begin
      j:=i;i:=pre[i];x:=now[j];
      t[x].lim:=t[x].lim-dx;
      x:=t[x].other;t[x].lim:=t[x].lim+dx;
    end;
  end;
  writeln(ans);
  close(output);
end;
begin
  init;
  work;
end.
 
 

ff】
program napkin;
const
  fin = 'napkin.in';
  fout = 'napkin.out';
  maxn = 1002;
type
  pnode = ^tnode; {定义弧类型}
  tnode = record
    p, limit, flow, cost : integer; {p是弧终点,limit容量,flow流量,cost费用}
    next, other : pnode; {next指向下一条弧,other指向反向弧}
  end;
var
  n : integer;
  result : longint; {答案}
  map : array[1 .. maxn * 2 + 2] of pnode; {网络流图}
procedure insert(x, y, limit, cost : integer); {插入弧}
var
  tmp : pnode;
begin
  new(tmp); tmp^.p := y; tmp^.limit := limit; tmp^.cost := cost; tmp^.flow := 0;
  tmp^.next := map[x]^.next; map[x]^.next := tmp;
  new(tmp^.other); tmp^.other^.other := tmp; tmp := tmp^.other;
  tmp^.p := x; tmp^.limit := 0; tmp^.flow := 0; tmp^.cost := -cost;
  tmp^.next := map[y]^.next; map[y]^.next := tmp;
end;
procedure prepare; {读入}
var
  i, x, a, b, f, fa, fb : integer;
begin
  assign(input, fin); reset(input);
  readln(n, a, b, f, fa, fb);
  for i := 1 to n * 2 + 2 do begin
    new(map[i]); map[i]^.next := nil; map[i]^.other := nil;
  end;
  for i := 1 to n do begin
    read(x);
    insert(1, i + 1, x, 0); {第1类弧}
    insert(i + 1, n + n + 2, maxint, f); {第2类弧}
    if i + n - a >= n + 2 then insert(i + 1, i + n - a, maxint, fa); {第3类弧}
    if i + n - b >= n + 2 then insert(i + 1, i + n - b, maxint, fb); {第4类弧}
    if i + n >= n + 2 then insert(i + n + 1, i + n, maxint, 0); {第5类弧}
    insert(i + n + 1, n + n + 2, x, 0); {第6类弧}
  end;
  close(input);
  result := 0;
  n := n * 2 + 2;
end;
procedure print; {输出}
begin
  assign(output, fout); rewrite(output);
  writeln(result);
  close(output);
end;
procedure maxflow; {最小费用最大流}
var
  delta, i, j : integer;
  tmp : pnode;
  more : boolean;
  value : longint;
  best, last : array[1 .. maxn * 2 + 2] of integer;
  save : array[1 .. maxn * 2 + 2] of pnode;
begin
  repeat
    fillchar(last, sizeof(last), 0);
    for i := 1 to n do best[i] := maxint;
    best[1] := 0; last[1] := maxint;
    repeat
      more := false;
      for i := 1 to n do if best[i] <> maxint then begin
        tmp := map[i]^.next;
        while tmp <> nil do begin
          if tmp^.flow < tmp^.limit then begin
            value := best[i] + tmp^.cost;
            if value < best[tmp^.p] then begin
              best[tmp^.p] := value; last[tmp^.p] := i;
              save[tmp^.p] := tmp; more := true;
            end;
          end;
          tmp := tmp^.next;
        end;
      end;
    until not more; {寻找最优可改进路}
    if best[n] = maxint then break;
    i := n; delta := maxint;
    repeat
      j := i; i := last[j]; tmp := save[j];
      if tmp^.limit - tmp^.flow < delta then delta := tmp^.limit - tmp^.flow;
    until i = 1; {求可改进量}
    result := result + best[n] * delta;
    i := n;
    repeat
      j := i; i := last[j]; tmp := save[j];
      tmp^.flow := tmp^.flow + delta;
      tmp^.other^.flow := -tmp^.flow;
    until i = 1; {放大流}
  until false;
end;
begin
  prepare; {输入}
  maxflow; {处理}
  print; {输出}
end.
 

文章来源于网络
了解更多资讯可关注天科学堂自主招生网(www.goodedus.com)、微信公众号【jingsai985】和奥林匹克学科竞赛网(www.jingsai985.com

本页标题:费用流算法效率比较[转]
本页网址:http://www.noip.org.cn//news/view.php?id=770
信息原创:中学生信息学竞赛网,版权所有,转载请注明出处,并以链接形式链接网址:http://www.noip.org.cn/
上一个  :  noi(省选)应该掌握的知识点
下一个  :  信息学奥赛分区联赛复赛经验漫谈