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

``` 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
12      fillchar(map,sizeof(map),0);
13      for i:=1 to m do
14          begin
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 时，暂且不考虑邻接矩阵...

• ### 1059: [ZJOI2007]矩阵游戏

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

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

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

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

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

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

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

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

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

• ### python自带的卷积

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

• ### LaTeX系列：基本框架

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

• ### 我用 Java 8 写了一段逻辑，同事直呼看不懂，你试试看。。

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