算法模板——Dinic最小费用最大流

实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用

其实相当的像Dinic最大流呐= =

还是spfa处理出最短路径(注意,这次是最短路径,所以时空复杂度将有所提高,害得我都开循环队列了TT),然后顺着最短路径顺藤摸瓜找回去,求出流大小和最小的费用,然后,没有然后了,程序还是一样的好懂么么哒(HansBug:感觉Dinic算法真心超级喜感,为啥我之前就没发现呢= =,还有鸣谢wnjxyk神犇提供的C++模板么么哒 Wnjxyk:^_^)

(本程序为BZOJ1927的AC程序,模板题么么哒,还有其实感觉spfa函数里面每次清空e数组貌似不是很必要,但还是图个安心写下吧)

 1 const maxl=100000;
 2 type
 3     point=^node;
 4     node=record
 5                g,w,f:longint;
 6                next,anti:point;
 7     end;
 8 var
 9    a,e:array[0..10000] of point;
10    i,j,k,l,m,n,s,t,ans,flow:longint;
11    c,g:array[0..10000] of longint;
12    d:array[0..maxl] of longint;
13 function min(x,y:longint):longint;
14          begin
15               if x<y then min:=x else min:=y;
16          end;
17 procedure swap(var x,y:longint);
18           var z:longint;
19           begin
20                z:=x;x:=y;y:=z;
21           end;
22 procedure add(x,y,z,t:longint);
23           var p:point;
24           begin
25                new(p);p^.g:=y;p^.w:=z;p^.f:=t;p^.next:=a[x];a[x]:=p;
26                new(p);p^.g:=x;p^.w:=0;p^.f:=-t;p^.next:=a[y];a[Y]:=p;
27                a[x]^.anti:=a[y];a[y]^.anti:=a[x];
28           end;
29 function spfa:boolean;     //神(dou)奇(bi)的最短路径预处理
30          var f,r:longint;p:point;
31          begin
32               for i:=s to t do c[i]:=maxlongint;
33               for i:=s to t do e[i]:=nil;
34               d[1]:=s;f:=1;r:=2;g[s]:=1;c[s]:=0;
35               while f<>r do
36                     begin
37                          p:=a[d[f]];
38                          while p<>nil do
39                                begin
40                                     if (p^.w<>0) and (c[p^.g]>(c[d[f]]+p^.f)) then
41                                        begin
42                                             c[p^.g]:=c[d[f]]+p^.f;
43                                             e[p^.g]:=p;
44                                             if g[p^.g]=0 then
45                                                begin
46                                                     g[p^.g]:=1;
47                                                     d[r]:=p^.g;r:=(r mod maxl)+1;
48                                                end;
49                                        end;
50                                     p:=p^.next;
51                                end;
52                          g[d[f]]:=0;f:=(f mod maxl)+1;
53                     end;
54               exit(c[t]<>maxlongint);
55          end;
56 procedure calc;
57           begin
58                l:=maxlongint;
59                i:=t;
60                while i<>s do
61                      begin
62                           l:=min(l,e[i]^.w);
63                           i:=e[i]^.anti^.g;   //当前弧的反向弧所指向的点就是你要回到的点^_^
64                      end;
65                i:=t;inc(flow,l);
66                while i<>s do
67                      begin
68                           if e[i]^.w<>maxlongint then dec(e[i]^.w,l);
69                           if e[i]^.anti^.w<>maxlongint then inc(e[i]^.anti^.w,l);
70                           inc(ans,e[i]^.f*l);
71                           i:=e[i]^.anti^.g;
72                      end;
73           end;
74 begin
75      readln(n,m);s:=0;t:=2*n+1;
76      for s:=0 to t do a[i]:=nil;
77      for i:=1 to n do
78          begin
79               read(l);
80               add(0,i,1,0);
81               add(i+n,t,1,0);
82               add(0,i+n,1,l);
83          end;
84      readln;
85      for i:=1 to m do
86          begin
87               readln(j,k,l);
88               if j>k then swap(j,k);
89               add(j,k+n,1,l);
90          end;
91      flow:=0;ans:=0; //flow表示最大流;ans表示最小费用
92      while spfa do calc;
93      writeln(ans);
94      readln;
95 end.

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Fish

CUDA C最佳实践-CUDA Best Practices(三)

10. 运行配置优化 10.1. 占用 10.1.1. 计算占用 10.2. 同步Kernel执行 10.3. 多上下文 10.4. 隐藏寄存器依赖 10.5....

264100
来自专栏利炳根的专栏

学习笔记TF063:TensorFlow Debugger

TensorFlow Debugger(tfdbg),TensorFlow专用调试器。用断点、计算机图形化展现实时数据流,可视化运行TensorFlow图形内部...

66300
来自专栏和蔼的张星的图像处理专栏

DSP图像处理

最近着手把CSK移植到DSP中,先看一些DSP中图像处理的一些例子,第一件事当然就是怎么把图像数据倒入CCS工程中了,去年倒是用过一点CCS,再拿起来已经忘得差...

30320
来自专栏SeanCheney的专栏

《Python数据分析》2nd

《Python数据分析》(Python for Data Analysis, 2nd Edition)第二版出了,目前还没有中文版,这版的代码适用于Python...

42480
来自专栏李海辰的专栏

Unity 引擎资源管理代码分析 ( 1 )

目前网络上已经有很多介绍 Unity 资源管理机制、和 API 使用方法的文章,但少有文章从 Unity源码层面对其实现进行深度解析。作为一名喜欢打破砂锅璺到底...

1.4K10
来自专栏落影的专栏

OpenGLES进阶教程8-obj文件和mtl文件解析

教程 距离上一篇教程已经有两个月了,这两个月详细阅读GPUImage的源码,并写了详细解析,发现对OpenGLES的深入了解很有帮助。 上周一个简书的朋友问我...

44870
来自专栏Python中文社区

Python量子力学计算模拟以及数据可视化

專 欄 ❈Pytlab,Python 中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,...

1K90
来自专栏简书专栏

Python数据分析及可视化-小测验

本文中测验需要的文件夹下载链接: https://pan.baidu.com/s/1OqFM2TNY75iOST6fBlm6jw 密码: rmbt 下载压缩包...

33420
来自专栏生信宝典

R语言学习 - 箱线图一步法

箱线图 - 一步绘制 绘图时通常会碰到两个头疼的问题: 有时需要绘制很多的图,唯一的不同就是输入文件,其它都不需要修改。如果用R脚本,需要反复替换文件名,繁琐又...

38550
来自专栏数据库

《数据库系统概念》15-可扩展动态散列

静态散列要求桶的数目始终固定,那么在确定桶数目和选择散列函数时,如果桶数目过小,随着数据量增加,性能会降低;如果留一定余量,又会带来空间的浪费;或者定期重组散列...

35670

扫码关注云+社区

领取腾讯云代金券