专栏首页HansBug's Lab算法模板——sap网络最大流 3(递归+邻接矩阵)

算法模板——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 条评论
登录 后参与评论

相关文章

  • 算法模板——平衡树Treap 2

    实现功能:同平衡树Treap 1(BZOJ3224 / tyvj1728) 这次的模板有了不少的改进,显然更加美观了,几乎每个部分都有了不少简化,尤其是删除部分...

    HansBug
  • 算法模板——sap网络最大流 3(递归+邻接表)

    实现功能:同前 程序还是一如既往的优美,虽然比起邻接矩阵的稍稍长了那么些,不过没关系这是必然,但更重要的一个必然是——速度将是一个质的飞跃^_^(这里面的poi...

    HansBug
  • 关于一般的并查集求根操作的一组对照研究

    说道并查集,大家一定对于以多叉树状结构为基础的并查集并不陌生,最常见的两种写法如下 1 function getfat(x:longint):longint; ...

    HansBug
  • 数字资产量化交易系统开发技术的三个主要特征

    近几年随着各种数字资产的崛起数字资产量化交易系统(开发)也得到了一定的发展,比特币价格的猛涨以及区块链技术的大火,以及各方有关于区块链的有利消息的不断输出,数字...

    场外交易所开发
  • 一张图掌握全部find命令用法

    作者: 逃跑中计划 来源:http://www.jianshu.com/p/948f1b67a910

    小小科
  • AWS事故总结,几招教你规避风险

    腾讯云对象存储服务基于多年海量数据存储的经验,针对企业应对人为误操作、软件错误、病毒入侵等“软”性灾害和硬件故障、自然灾害等“硬”性灾害,应该如何实现稳定的容灾...

    王煜奕
  • iOS开发小点·移除所有子视图

    陈满iOS
  • 《指数基金投资指南》第2章 投资工具这么多,为什么要选指数基金

    yeedomliu
  • 欢迎挑战!14个数据分析和机器学习项目!附数据集

    对于那些对数据,数据分析或数据科学感兴趣的人,提供一份可以利用业余时间完成的数据科学项目清单,一共14个!

    统计学家
  • 隔离太无聊?每天一个数据科学项目,数据集都准备好了!

    首先,我想向所有的护士,医生,超市员工,公共管理人员以及其他冒着生命危险为我们服务的人致敬。

    大数据文摘

扫码关注云+社区

领取腾讯云代金券