算法模板——sap网络最大流 3(递归+邻接矩阵)

实现功能:同之前

可以看见的是这次的程序优美了许多,代码简短了一倍还多,可是速度却是和原来的邻接表一个级别的(在Codevs上面草地排水那题的运行时间比较,但是显然数据很大时应该比那个慢些),原理差不多,感觉dfs里面的来回倒变量很神奇

 1 var
 2    s,t,i,j,k,l,m,n,ans:longint;
 3    a:array[0..1000,0..1000] of longint;
 4    d,dv:array[0..10000] of longint;
 5 function min(x,y:longint):longint;inline;
 6          begin
 7               if x<y then min:=x else min:=y;
 8          end;
 9 function dfs(x,flow:longint):longint;inline;
10          var i,j,k,l:longint;
11          begin
12               if x=t then exit(flow);
13               dfs:=0;
14               for i:=1 to n do
15                   if (a[x,i]>0) and (d[x]=(d[i]+1)) then
16                      begin
17                           k:=dfs(i,min(flow-dfs,a[x,i]));
18                           dec(a[x,i],k);
19                           inc(a[i,x],k);
20                           inc(dfs,k);
21                           if dfs=flow then exit;
22                      end;
23               if d[s]=n then exit;
24               dec(dv[d[x]]);
25               if dv[d[x]]=0 then d[s]:=n;
26               inc(d[x]);
27               inc(dv[d[x]]);
28          end;
29 begin
30      readln(n,m,s,t);
31      fillchar(a,sizeof(a),0);
32      for i:=1 to m do
33          begin
34               readln(j,k,l);
35               inc(a[j,k],l);
36          end;
37      fillchar(d,sizeof(d),0);
38      fillchar(dv,sizeof(dv),0);
39      dv[0]:=n;ans:=0;
40      while d[s]<n do inc(ans,dfs(s,maxlongint));
41      writeln(ans);
42 end.           

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏极乐技术社区

小程序 · 一周报 | 小程序获取用户信息接口优化调整 / 小游戏视频广告发布

18820
来自专栏美团技术团队

行进中换轮胎——万字长文解析美团和大众点评两大数据平台是怎么融合的

背景 互联网格局复杂多变,大规模的企业合并重组不时发生。原来完全独立甚至相互竞争的两家公司,有着独立的技术体系、平台和团队,如何整合,技术和管理上的难度都很大。...

406170
来自专栏FreeBuf

什么是集中管控式大数据安全架构?

大数据已不再是一个单纯的热门词汇了,随着技术的发展大数据已在企业、政府、金融、医疗、电信等领域得到了广泛的部署和应用,并通过持续不断的发展,大数据也已在各领域产...

29160
来自专栏linux、Python学习

你到底懂不懂什么是Linux运维工程师?

作为互联网的幕后英雄,Linux运维工程师长期隐匿在大众认知范围之外,关于运维的讨论仍旧是一片无人涉足的荒漠。在某知名行业研究调查结果中,非互联网从业者对于运维...

34720
来自专栏编程一生

《静儿的服务治理私房菜》服务治理和架构

12220
来自专栏WeTest质量开放平台团队的专栏

你的手游遭遇信任危机了吗?从XcodeGhost漏洞事件看手游安全测试

这两天的安全领域被一个词刷屏了,XcodeGhost,这种病毒不仅会在应用运行时窃取用户信息,甚至还会模拟收费或帐号弹窗来窃取你的iCloud及iTunes密码...

10120
来自专栏BIT泽清

IOS提审金融理财小额贷App被拒,怎么修改代码才能通过?

5月份,越来越多的金融理财期货贷款类APP更新时都收到了iOS应用商店被拒的信息(《应用商店评论指南》5.2.1条例)(2.1大礼包的问题也非常多)。基本上都是...

33760
来自专栏喔家ArchiSelf

全栈的技术栈设想

参加今年的SDCC确实挺高兴的,向大师Joe Armstrong 当面求教,与周爱民老师同台,在我们的架构师进阶之路专场有4个七零后的老码农,瞬间没有了孤独感,...

13030
来自专栏魏艾斯博客www.vpsss.net

腾讯云新购云服务器五折 1 核 1G 3 年 794.73 元(即 265 元/年)

68740
来自专栏数据库新发现

DBA2.0的时代 - DBA将向何处去?

最近接触和参与了很多关于DBA职业生涯发展的讨论,也有很多朋友问过我,DBA将向何处去? 思考了很多,在这里和大家分享一下关于DBA的我的看法。

14110

扫码关注云+社区

领取腾讯云代金券