算法模板——Dinic最小费用最大流

（本程序为BZOJ1927的AC程序，模板题么么哒,还有其实感觉spfa函数里面每次清空e数组貌似不是很必要，但还是图个安心写下吧）

1 const maxl=100000;
2 type
3     point=^node;
4     node=record
5                g,w,f:longint;
6                next,anti:point;
7     end;
8 var
9    a,e:array[0..10000] of point;
10    i,j,k,l,m,n,s,t,ans,flow:longint;
11    c,g:array[0..10000] of longint;
12    d:array[0..maxl] of longint;
13 function min(x,y:longint):longint;
14          begin
15               if x<y then min:=x else min:=y;
16          end;
17 procedure swap(var x,y:longint);
18           var z:longint;
19           begin
20                z:=x;x:=y;y:=z;
21           end;
23           var p:point;
24           begin
25                new(p);p^.g:=y;p^.w:=z;p^.f:=t;p^.next:=a[x];a[x]:=p;
26                new(p);p^.g:=x;p^.w:=0;p^.f:=-t;p^.next:=a[y];a[Y]:=p;
27                a[x]^.anti:=a[y];a[y]^.anti:=a[x];
28           end;
29 function spfa:boolean;     //神(dou)奇(bi)的最短路径预处理
30          var f,r:longint;p:point;
31          begin
32               for i:=s to t do c[i]:=maxlongint;
33               for i:=s to t do e[i]:=nil;
34               d[1]:=s;f:=1;r:=2;g[s]:=1;c[s]:=0;
35               while f<>r do
36                     begin
37                          p:=a[d[f]];
38                          while p<>nil do
39                                begin
40                                     if (p^.w<>0) and (c[p^.g]>(c[d[f]]+p^.f)) then
41                                        begin
42                                             c[p^.g]:=c[d[f]]+p^.f;
43                                             e[p^.g]:=p;
44                                             if g[p^.g]=0 then
45                                                begin
46                                                     g[p^.g]:=1;
47                                                     d[r]:=p^.g;r:=(r mod maxl)+1;
48                                                end;
49                                        end;
50                                     p:=p^.next;
51                                end;
52                          g[d[f]]:=0;f:=(f mod maxl)+1;
53                     end;
54               exit(c[t]<>maxlongint);
55          end;
56 procedure calc;
57           begin
58                l:=maxlongint;
59                i:=t;
60                while i<>s do
61                      begin
62                           l:=min(l,e[i]^.w);
63                           i:=e[i]^.anti^.g;   //当前弧的反向弧所指向的点就是你要回到的点^_^
64                      end;
65                i:=t;inc(flow,l);
66                while i<>s do
67                      begin
68                           if e[i]^.w<>maxlongint then dec(e[i]^.w,l);
69                           if e[i]^.anti^.w<>maxlongint then inc(e[i]^.anti^.w,l);
70                           inc(ans,e[i]^.f*l);
71                           i:=e[i]^.anti^.g;
72                      end;
73           end;
74 begin
76      for s:=0 to t do a[i]:=nil;
77      for i:=1 to n do
78          begin
83          end;
85      for i:=1 to m do
86          begin
88               if j>k then swap(j,k);
90          end;
91      flow:=0;ans:=0; //flow表示最大流；ans表示最小费用
92      while spfa do calc;
93      writeln(ans);
95 end.

0 条评论

• 算法模板——Dinic网络最大流 2

实现功能：同Dinic网络最大流 1 这个新的想法源于Dinic费用流算法。。。 在费用流算法里面，每次处理一条最短路，是通过spfa的过程中就记录下来，然后顺...

• 算法模板——线段树7（骰子翻转问题）

实现功能：首先输入一个长度为N的序列，由1-4组成（1表示向前滚一下，2表示向后滚一下，3表示向左滚一下，4表示向右滚一下，骰子原始状态：上1前2左4右5后3下...

• 3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

• 算法模板——Dinic网络最大流 2

实现功能：同Dinic网络最大流 1 这个新的想法源于Dinic费用流算法。。。 在费用流算法里面，每次处理一条最短路，是通过spfa的过程中就记录下来，然后顺...

• 2292: 【POJ Challenge 】永远挑战

2292: 【POJ Challenge 】永远挑战 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 553 ...

• 1131: [POI2008]Sta

1131: [POI2008]Sta Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 783  Solved:...

• 2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 8  Solved: 8...

• 如何优雅关闭 Spring Boot 应用

随着线上应用逐步采用 SpringBoot 构建，SpringBoot应用实例越来多，当线上某个应用需要升级部署时，常常简单粗暴地使用 kill 命令，这种停止...

• 【iOS 开发】3分钟搭建 App Store 动态审核开关

我曾经在一篇文章中写过，希望大家不要欺骗 App Store Review Team，但是近来的 Uber 审核事件，以及发生在我个人身上的 审核团队不对我的长...

• MySQL row格式的两个问题

作者简介： ? 刘伟 云和恩墨开源解决方案事业部首席架构师 多年一线互联网企业DBA经历，对MySQL、NoSQL，PostgreSQL等各类开源数据库均有涉猎...