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

``` 1 type
2     point=^node;
3     node=record
4                g,w:longint;
5                next,anti:point;
6     end;
7 var
8    i,j,k,l,m,n,s,t,flow:longint;
9    a,e:array[0..10000] of point;
10    c,d:array[0..10000] of longint;
11 function min(x,y:longint):longint;
12          begin
13               if x<y then min:=x else min:=y;
14          end;
16           var p:point;
17           begin
18                new(p);p^.g:=y;p^.w:=z;p^.next:=a[x];a[x]:=p;
19                new(p);p^.g:=x;p^.w:=0;p^.next:=a[y];a[y]:=p;
20                a[x]^.anti:=a[y];a[y]^.anti:=a[x];
21           end;
22 function spfa:boolean;
23          var p:point;f,r:longint;
24          begin
25               fillchar(c,sizeof(c),255);
26               d[1]:=s;f:=1;r:=2;c[s]:=0;
27               while f<r do
28                     begin
29                          p:=a[d[f]];
30                          while p<>nil do
31                                begin
32                                     if (p^.w<>0) and (c[p^.g]=-1) then
33                                        begin
34                                             c[p^.g]:=c[d[f]]+1;
35                                             e[p^.g]:=p;
36                                             d[r]:=p^.g;inc(r);
37                                        end;
38                                     p:=p^.next;
39                                end;
40                          inc(f);
41                     end;
42               exit(c[t]<>-1);
43          end;
44 procedure calc;   //“顺藤摸瓜”模式有效避免了递归带来的爆栈隐患
45           begin
46                i:=t;l:=maxlongint;
47                while i<>s do
48                      begin
49                           l:=min(l,e[i]^.w);
50                           i:=e[i]^.anti^.g;
51                      end;
52                i:=t;inc(flow,l);
53                while i<>s do
54                      begin
55                           if e[i]^.w<>maxlongint then dec(e[i]^.w,l);
56                           if e[i]^.anti^.w<>maxlongint then inc(e[i]^.anti^.w,l);
57                           i:=e[i]^.anti^.g;
58                      end;
59           end;
60 begin
62      for i:=1 to n do a[i]:=nil;
63      for i:=1 to m do
64          begin
67          end;
68      flow:=0;while spfa do calc;
69      writeln(flow);
71 end.```

0 条评论

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

实现功能：输入M,N,S,T；接下来M行输入M条弧的信息（包括起点，终点，流量，单位费用）；实现功能是求出以S为源点，T为汇点的网络最大流的最小费用 其实相当的...

• 算法模板——线段树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最小费用最大流

实现功能：输入M,N,S,T；接下来M行输入M条弧的信息（包括起点，终点，流量，单位费用）；实现功能是求出以S为源点，T为汇点的网络最大流的最小费用 其实相当的...

• 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等各类开源数据库均有涉猎...