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

实现功能:同sap网络最大流

今天第一次学Dinic,感觉最大的特点就是——相当的白话,相当的容易懂,而且丝毫不影响复杂度,顶多也就是代码长个几行

主要原理就是每次用spfa以O(n)的时间复杂度预处理出层次图,然后像sap一样深搜一下,搞定。。。代码相当好懂

 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;
15 procedure add(x,y,z:longint);
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
62      readln(m,n);s:=1;t:=n;
63      for i:=s to t do a[i]:=nil;
64      for i:=1 to m do
65          begin
66               readln(j,k,l);
67               add(j,k,l);
68          end;
69      ans:=0;
70      while spfa do inc(ans,dfs(s,maxlongint));
71      writeln(ans);
72      readln;
73 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1026: [SCOI2009]windy数(数位dp)

1082
来自专栏自动化测试实战

flask第十二篇——自定义url转换器【2】

29613
来自专栏Java架构师学习

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

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

3765
来自专栏JetpropelledSnake

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

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

4276
来自专栏撸码那些事

【抽象那些事】不完整的抽象&多方面抽象&未用的抽象&重复的抽象

一种重要的抽象实现手法是创建内聚而完整的抽象。抽象未支持相关的方法时,可能会影响抽象的内聚性和完整性。如果抽象只支持部分相关的方法,其使用者就可能不得不自己去实...

1739
来自专栏圣杰的专栏

DDD理论学习系列(11)-- 工厂

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

26610
来自专栏张善友的专栏

微软在动态语言支持上超越了Java?

当.NET在2000/2001年第一次发布的时候,Java社区认为它仅仅是从语言以及标准库上对Java的一个“克隆”。我们把二者的简单实例代码进行比较以后就可以...

18810
来自专栏Java架构

每个 JavaScript 工程师都应当知道的 10 个面试题以人为本1. 能说出来两种对于 JavaScript 工程师很重要的编程范式么?2. 什么是函数式编程?3. 类继承和原型继承有什么区别?

2916
来自专栏函数式编程语言及工具

Akka(0):聊聊对Akka的初步了解和想法

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

2548
来自专栏FreeBuf

扒一扒基于词法分析和语法分析的SQL注入攻击检测

周末了,又到了一星期中的美好时刻,因为期待,因为渲染在时光中的慵散。本周,Black Hat大会,应该是安全界中的大事件。 这不,经过一番紧锣密鼓的搜罗,发现了...

6018

扫码关注云+社区

领取腾讯云代金券