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

相关文章

来自专栏用户2442861的专栏

caffe python 图片训练识别 实例

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details...

7192
来自专栏BestSDK

MXNet Scala发布图像分类API|附使用教程

这次发布的 Scala,里面的推理应用程序致力于优化开发者体验。Scala 是一个通用目的程序语言,支持功能性编程和较强的静态类型系统,它被用于平台的高度分布式...

1387
来自专栏人工智能LeadAI

pytorch入门教程 | 第四章:准备图片数据集

在训练神经网络之前,我们必须有数据,作为资深伸手党,必须知道以下几个数据提供源: 1 CIFAR-10 ? CIFAR-10图片样本截图 CIFAR-10是多...

9828
来自专栏崔庆才的专栏

3个关键点,把你的TensorFlow代码重构为分布式!

1563
来自专栏破晓之歌

神经网络简介 原

934
来自专栏ATYUN订阅号

保存并加载您的Keras深度学习模型

Keras是一个用于深度学习的简单而强大的Python库。 鉴于深度学习模式可能需要数小时、数天甚至数周的时间来培训,了解如何保存并将其从磁盘中加载是很重要的...

5966
来自专栏深度学习与计算机视觉

手把手教你如何应用TF-Slim快速实现迁移学习

这是一篇以实践为主的入门文章,目的在于用尽量少的成本组织起来一套可以训练和测试自己的分类任务的代码,其中就会用到迁移学习,TF-Slim库的内容,所以我们分为下...

1.1K8
来自专栏AI科技大本营的专栏

实战 | 手把手教你用苹果CoreML实现iPhone的目标识别

在WWDC 2017上,苹果首次公布了机器学习方面的动作。iOS系统早已支持Machine Learning 和 Computer Vision ,但这次苹果提...

8108
来自专栏生信技能树

【r<-ROC|包】分析与可视化ROC——plotROC、pROC

在【r<-绘图|ROC】ROC的计算与绘制这篇文章中我讲了ROC曲线的本质以及如何计算和绘制ROC曲线。注意,我这里谈到的ROC并未曾涉及机器学习模型的拟合与预...

2082
来自专栏小石不识月

如何将机器学习模型转移到产品中

针对于特定问题(例如自然语言处理,即 NLP,或图像识别)的深度学习模型开发、训练和调参,需要耗费时间与资源。这通常还包括使用功能强大的处理器来训练大型数据集上...

7892

扫码关注云+社区

领取腾讯云代金券