# 算法模板——Dinic网络最大流 1

``` 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,ans:longint;
9    a: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;   //spfa预处理出层次图，同时检测连通性
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                                             d[r]:=p^.g;
36                                             inc(r);
37                                        end;
38                                     p:=p^.next;
39                                end;
40                          inc(f);
41                     end;
42               exit(c[t]<>-1);
43          end;
44 function dfs(x,flow:longint):longint;   //像sap一样的DFS么么哒
45          var p:point;k:longint;
46          begin
47               if x=t then exit(flow);
48               dfs:=0;p:=a[x];
49               while p<>nil do
50                     begin
51                          if (p^.w<>0) and ((c[x]+1)=c[p^.g]) then
52                             begin
53                                  k:=dfs(p^.g,min(flow-dfs,p^.w));
54                                  if p^.w<>maxlongint then dec(p^.w,k);
55                                  if p^.anti^.w<>maxlongint then inc(p^.anti^.w,k);
56                                  inc(dfs,k);if dfs=flow then exit;
57                             end;
58                          p:=p^.next;
59                     end;
60          end;
61 begin
63      for i:=s to t do a[i]:=nil;
64      for i:=1 to m do
65          begin
68          end;
69      ans:=0;
70      while spfa do inc(ans,dfs(s,maxlongint));
71      writeln(ans);
73 end.```

251 篇文章37 人订阅

0 条评论

## 相关文章

1082

29613

### 2017年终巨献阿里、腾讯最新Java程序员面试题，准备好进BAT了吗

Java基础 进程和线程的区别； Java的并发、多线程、线程模型； 什么是线程池，如何使用? 数据一致性如何保证；Synchronized关键字，类锁，方法锁...

3765

### Python入门之实现简单的购物车功能

Talk is cheap，Let's do this! product_list = [ ['Iphone7 Plus', 6500], ['...

4276

1739

### DDD理论学习系列（11）-- 工厂

1.引言 在针对大型的复杂领域进行建模时，聚合、实体和值对象之间的依赖关系可能会变得十分复杂。在某个对象中为了确保其依赖对象的有效实例被创建，需要深入了解对象实...

26610

18810

2916

### Akka（0）：聊聊对Akka的初步了解和想法

前一段时间一直沉浸在函数式编程模式里，主要目的之一是掌握一套安全可靠的并发程序编程方法（concurrent programming），最终通过开源项目F...

2548

6018