dinic算法 c 语言,网络流入门—用于最大流的Dinic算法

r囧r小猫 2022-10-15 05:54 208阅读 0赞

“网络流博大精深”—sideman语

![L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9kaXRjaDEucG5n.jpg][]

一个基本的网络流问题

最早知道网络流的内容便是最大流问题，最大流问题很好理解：

解释一定要通俗!

如右图所示,有一个管道系统,节点\{1,2,3,4\},有向管道\{A,B,C,D,E\},即有向图一张. \[1\]是源点,有无限的水量,\[4\]是汇点,管道容量如图所示.试问\[4\]点最大可接收的水的流量?

这便是简单的最大流问题,显然\[4\]点的最大流量为50

死理性派请注意:流量是单位时间内的,总可以了吧!

然而对于复杂图的最大流方法是什么呢,有EK,Dinic,SAP,etc.下面介绍Dinic算法(看代码的直接点这)

Dinic 算法

Dinic算法的基本思路:

根据残量网络计算层次图。

在层次图中使用DFS进行增广直到不存在增广路

重复以上步骤直到无法增广

引自NOCOW,相当简单是吧...

小贴士:

一般情况下在Dinic算法中,我们只记录某一边的剩余流量.

残量网络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量网络,

层次图:分层图,以\[从原点到某点的最短距离\]分层的图,距离相等的为一层,(比如上图的分层为\{1\},\{2,4\},\{3\})

DFS:这个就不用说了吧...

增广  :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差)

增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?)

剩余流量:当一条边被增广之后(即它是增广路的一部分,或者说增广路通过这条边),这条边还能通过的流量.

反向弧:我们在Dinic算法中,对于一条有向边,我们需要建立另一条反向边(弧),当正向(输入数据)边剩余流量减少I时,反向弧剩余流量增加I

Comzyh的较详细解释(流程) :

注意(可以无视):用BFS建立分层图  注意:分层图是以当前图为基础建立的,所以要重复建立分层图

用DFS的方法寻找一条由源点到汇点的路径,获得这条路径的流量I

根据这条路径修改整个图,将所经之处正向边流量减少I,反向边流量增加I,注意I是非负数

重复步骤2,直到DFS找不到新的路径时,重复步骤1

Dinic(其实其他的好多)算法中寻找到增广路后要将反向边增加I

Dinic中DFS时只在分层图中DFS，意思是说DFS的下一个节点的Dis(距源点的距离)要比自己的Dis大1,例如在图1中第一个次DFS中,1->2->4 这条路径是不合法的,因为Dis\[2\]=1;Dis\[4\]=1;

步骤2中"获得这条路径的流量I "实现:DFS函数有参量low,代表从源点到现在最窄的(剩余流量最小)的边的剩余流量,当DFS到汇点是,Low便是我们要的流量I

对于反向弧(反向边)的理解:

这一段不理解也不是不可以,对于会写算法没什么帮助,如果你着急,直接无视即可.

先举一个例子(如右图):

![L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9OZXRGbG93MS5wbmc=.jpg][L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9OZXRGbG93MS5wbmc_.jpg]

必须使用反向弧的流网络

在这幅图中我们首先要增广1->2->4->5,这时可以获得一个容量为2的流,但是如果不建立4->2反向弧的话,则无法进一步增广,最终答案为2,显然是不对的,然而如果建立了反向弧4->2,则第二次能进行1->3->4->2->5->6的增广,最大流为3.

Comzyh对反向弧的理解可以说是"偷梁换柱",请仔细阅读:在上面的例子中,我们可以看出,最终结果是1->2->5->6和1->2->4->6和1->3->4->6.当增广完1->2->4->5(代号A)后,在增广1->3->4->2->5->6(代号B),相当于将经过节点2的A流从中截流1(总共是2)走2->5>6,而不走2->4>6了,同时B流也从节点4截流出1(总共是1)走4->6而不是4->2->5->6,相当于AB流做加法.

简单的说反向弧为今后提供反悔的机会,让前面不走这条路而走别的路.

Dinic算法的程序实现

给出这道题的代码:

/\*

Program:POJ 1273 /

Dinic

Author:Comzyh

\*/

\#include

\#define min(x,y) ((x

using namespace std;

const int MAX=0x5fffffff;//

int tab\[250\]\[250\];//邻接矩阵

int dis\[250\];//距源点距离,分层图

int q\[2000\],h,r;//BFS队列 ,首,尾

int N,M,ANS;//N:点数;M,边数

int BFS()

int i,j;

memset(dis,0xff,sizeof(dis));//以-1填充

dis\[1\]=0;

h=0;r=1;

q\[1\]=1;

while (h

j=q\[++h\];

for (i=1;i<=N;i++)

if (dis\[i\]<0 && tab\[j\]\[i\]>0)

dis\[i\]=dis\[j\]+1;

q\[++r\]=i;

if (dis\[N\]>0)

return 1;

else

return 0;//汇点的DIS小于零,表明BFS不到汇点

//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广

int find(int x,int low)//Low是源点到现在最窄的(剩余流量最小)的边的剩余流量

int i,a=0;

if (x==N)return low;//是汇点

for (i=1;i<=N;i++)

if (tab\[x\]\[i\] >0 //联通

&& dis\[i\]==dis\[x\]+1 //是分层图的下一层

&&(a=find(i,min(low,tab\[x\]\[i\]))))//能到汇点(a <> 0)

tab\[x\]\[i\]-=a;

tab\[i\]\[x\]+=a;

return a;

return 0;

int main()

//freopen("ditch.in" ,"r",stdin );

//freopen("ditch.out","w",stdout);

int i,j,f,t,flow,tans;

while (scanf("%d%d",&M,&N)!=EOF)\{

memset(tab,0,sizeof(tab));

for (i=1;i<=M;i++)

scanf("%d%d%d",&f,&t,&flow);

tab\[f\]\[t\]+=flow;

ANS=0;

while (BFS())//要不停地建立分层图,如果BFS不到汇点才结束

while(tans=find(1,0x7fffffff))ANS+=tans;//一次BFS要不停地找增广路,直到找不到为止

printf("%d\\n",ANS);

system("pause");

【网络流相关】最大流的Dinic算法实现

Luogu P3376 于\\(EK\\)算法求最大流时每一次只求一条增广路,时间复杂度会比较高.尽管实际应用中表现比较优秀,但是有一些题目还是无法通过. 那么我们就会使用\\(Dinic\\)算法实现多路增 ...

浅谈最大流的Dinic算法

PART 1 什么是网络流 网络流(network-flows)是一种类比水流的解决问题方法,与线性规划密切相关.网络流的理论和应用在不断发展,出现了具有增益的流.多终端流.多商品流以及网络流的分解与 ...

【最大流之Dinic算法】POJ1273 【 &amp&semi; 当前弧优化 &amp&semi; 】

总评一句:Dinic算法的基本思想比较好理解,就是它的当前弧优化的思想,网上的资料也不多,所以对于当前弧的优化,我还是费了很大的功夫的,现在也一知半解,索性就写一篇博客,来发现自己哪里的算法思想还没理 ...

HDU1532最大流 Edmonds-Karp&comma;Dinic算法 模板

Drainage Ditches Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) To ...

POJ 1459 Power Network&lpar;网络最大流，dinic算法模板题&rpar;

题意:给出n,np,nc,m,n为节点数,np为发电站数,nc为用电厂数,m为边的个数.      接下来给出m个数据(u,v)z,表示w(u,v)允许传输的最大电力为z:np个数据(u)z,表示发电 ...

最大流：Dinic算法

蒟蒻居然今天第一次写网络流 我太弱啦! 最大流问题有很多解法 虽然isap常数巨小 但是连dinic都写挂的本蒟蒻并不会orz 那么我们选用比较好实现的dinic来解决最大流问题 来一段定义:    ...

网络流最大流——dinic算法

前言 网络流问题是一个很深奥的问题,对应也有许多很优秀的算法.但是本文只会讲述dinic算法 最近写了好多网络流的题目,想想看还是写一篇来总结一下网络流和dinic算法以免以后自己忘了... 网络流问 ...

网络流之最大流Dinic算法模版

/\* 网络流之最大流Dinic算法模版 \*/ \#include \#include \#include using ...

网络流入门--最大流算法Dicnic 算法

感谢WHD的大力支持 最早知道网络流的内容便是最大流问题,最大流问题很好理解: 解释一定要通俗! 如右图所示,有一个管道系统,节点\{1,2,3,4\},有向管道\{A,B,C,D,E\},即有向图一张. ...

随机推荐

Event Sourcing Pattern 事件源模式

Use an append-only store to record the full series of events that describe actions taken on data in ...

Httpsqs队列基本操作

一,安装 ulimit -SHn 65535 wget http://httpsqs.googlecode.com/files/libevent-2.0.12-stable.tar.gz tar zx ...

如何开发H5项目 -- 入门篇

前言 H5即HTML5,H5开发具有低成本.高效率.跨平台.研发周期短,用户接触成本低等特性. 一.开发环境 在开发一个H5项目之前,需要先搞好环境.主要有node.npm.gulp.bower.下面 ...

java微信接口之二—获取用户组

一.微信获取用户组接口简介 1.请求 该请求也是GET方式请求.请求的url格式如下: https://api.weixin.qq.com/cgi-bin/groups/get?access\_toke ...

max&lowbar;allowed&lowbar;packet

http://dev.mysql.com/doc/refman/5.7/en/comparison-operators.html\#function\_in SELECT val1 FROM tbl1 W ...

python&lowbar;列表

1.  列表的定义 (1) 用\[\]包含的元素,就是列表 (2)可以用list函数定义列表 2.  基本的列表操作(可参考示例) (1)元素赋值 (2)删除元素 (3)分片赋值 3. 列表方法 (1) ...

angular模板加载 ----ng-template

Angularjs作为mvc(或者说mvvm)框架,同样具备模板这一基本概念. NG加载模板的顺序为 内存加载---AJAX加载. 如果排版乱掉,请查阅https://www.zybuluo.com/ ...

Oracle 学习笔记(一)Oracle的基本介绍与语法

1.1 Oracle基础知识 1.1.1 介绍 Oracle数据库的主要特点: 支持多用户.大事务量的事务处理 在保持数据安全性和完整性方面性能优越 支持分布式数据处理 具有可移植性 1.1.2 Or ...

转：C&plus;&plus; 匿名namespace的作用以及它与static的区别

匿名namespace的作用以及它与static的区别 一.匿名namespace的作用在C语言中,如果我们在多个tu(translation unit)中使用了同一个名字做为函数名或者全局变量名,则 ...

UVALive 7352 Dance Recital

题意: 有n种舞蹈要跳 每种舞蹈需要每一行字符串所对应的那些人 如果一个人连着跳两个舞蹈 那么需要一个quick change 问需要的最少quick changes是多少 思路: 假期的题 又拿出来 ...

[L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9kaXRjaDEucG5n.jpg]: https://bbsmax.ikafan.com/static/L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9kaXRjaDEucG5n.jpg
[L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9OZXRGbG93MS5wbmc_.jpg]: https://bbsmax.ikafan.com/static/L3Byb3h5L2h0dHAvdXBsb2FkLmNvbXp5aC50ay93b3JkcHJlc3MvMjAxMS8wNS9OZXRGbG93MS5wbmc=.jpg