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

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

实现功能:首行输入N,M,S,T,代表这张图N个点,M条边,源点为S,汇点为T;接下来T行输入个边的出发点、终点和权值;输出最大流

原理:sap网络流算法(详见百度百科,个人觉得这个模板已经不错了,虽然本人暂时还未考虑引入邻接表进行优化)(推荐模板题:Codevs1993

 1 var
 2    i,j,k,l,m,n,ans,aug,s,t,tmp,jl,mi:longint;
 3    flag:boolean;
 4    vh,dis,di,his,pre:array[0..10000] of longint;
 5    map:array[0..2050,0..2050] of longint;
 6 function min(x,y:longint):longint;inline;
 7          begin
 8               if x<y then min:=x else min:=y;
 9          end;
10 begin
11      readln(n,m,s,t);
12      fillchar(map,sizeof(map),0);
13      for i:=1 to m do
14          begin
15               readln(j,k,l);
16               map[j,k]:=map[j,k]+l;
17          end;
18      i:=s;ans:=0;aug:=maxlongint;
19      fillchar(dis,sizeof(dis),0);
20      for i:=1 to n do di[i]:=1;
21      i:=s;
22      while dis[s]<n do
23            begin
24                 flag:=false;
25                 his[i]:=aug;
26                 for j:=di[i] to n do
27                     begin
28                          if (map[i,j]>0) and (dis[i]=(dis[j]+1)) then
29                             begin
30                                  aug:=min(aug,map[i,j]);
31                                  pre[j]:=i;di[i]:=j;
32                                  i:=j;flag:=true;
33                                  if i=t then
34                                     begin
35                                          ans:=ans+aug;
36                                          while i<>s do
37                                                begin
38                                                     tmp:=i;
39                                                     i:=pre[i];
40                                                     map[i,tmp]:=map[i,tmp]-aug;
41                                                     map[tmp,i]:=map[tmp,i]+aug;
42                                                end;
43                                          aug:=maxlongint;
44                                     end;
45                                  break;
46                             end;
47                     end;
48                 if flag then continue;
49                 jl:=-1;mi:=n-1;
50                 for j:=1 to n do
51                     begin
52                          if (map[i,j]>0) and (dis[j]<mi) then
53                             begin
54                                  mi:=dis[j];
55                                  jl:=j;
56                             end;
57                     end;
58                 di[i]:=jl;
59                 dec(vh[dis[i]]);
60                 if vh[dis[i]]=0 then break;
61                 dis[i]:=mi+1;
62                 inc(vh[dis[i]]);
63                 if i<>s then
64                    begin
65                         i:=pre[i];
66                         aug:=his[i];
67                    end;
68            end;
69      writeln(ans);
70 end.
71         

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    实现功能:同最大流 1 这里面主要是把前面的邻接矩阵改成了邻接表,相比之下速度大大提高——本人实测,当M=1000000 N=10000 时,暂且不考虑邻接矩阵...

    HansBug
  • 1059: [ZJOI2007]矩阵游戏

    1059: [ZJOI2007]矩阵游戏 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2154  Solv...

    HansBug
  • 1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

    1638: [Usaco2007 Mar]Cow Traffic 奶牛交通 Time Limit: 5 Sec  Memory Limit: 64 MB Sub...

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

    实现功能:同最大流 1 这里面主要是把前面的邻接矩阵改成了邻接表,相比之下速度大大提高——本人实测,当M=1000000 N=10000 时,暂且不考虑邻接矩阵...

    HansBug
  • TPU中的脉动阵列及其实现

    本文将对TPU中的矩阵计算单元进行分析,并给出了SimpleTPU中32×32的脉动阵列的实现方式和采用该阵列进行卷积计算的方法,以及一个卷积的设计实例...

    sea-wind
  • Xilinx Floating-Point Operator IP创建与仿真

    2>Precision of Inputs 我们选择单晶浮点数(Single),指数位宽Exponent Width 8bit 尾数位宽24 bit

    FPGA开源工作室
  • python自带的卷积

    ’full‘ 结果 [ 1 3 8 13 13 12] ’same‘结果[ 3 8 13 13] ’valid‘结果[ 8 13]

    py3study
  • 图论-网络流

    温安适
  • LaTeX系列:基本框架

    详细代码百度云链接:http://pan.baidu.com/s/1hrNF1Rm

    努力在北京混出人样
  • 我用 Java 8 写了一段逻辑,同事直呼看不懂,你试试看。。

    首先,业务需求是这样的,从第三方电商平台拉取所有订单,然后保存到公司自己的数据库,需要判断是否有物流信息,如果有物流信息,还需要再进行上传。

    Java技术栈

扫码关注云+社区

领取腾讯云代金券