返回顶部
首页 > 资讯 > 后端开发 > PHP编程 >网络流算法
  • 932
分享到

网络流算法

算法 2023-09-04 14:09:08 932人浏览 泡泡鱼
摘要

网络流 最大流的求法 我们对原图的每一条边再存储一条反向边,形成一个含有反向边的新图B。 起初反向边的容量为0,正向边的容量为原图中的容量。 每一次在图B上寻找一条从S->T的路径(注:该路径也就是增

网络

最大流的求法

我们对原图的每一条边再存储一条反向边,形成一个含有反向边的新图B。

起初反向边的容量为0,正向边的容量为原图中的容量。

每一次在图B上寻找一条从S->T的路径(注:该路径也就是增广路径),满足该路径上的每一条边的容量均不为0。

找到这条路径上的边的容量的最小值c,给这条路径上的所有边减去c,其反向边加上c。

直到不存在一条S->T的路径,满足该路径上的每一条边的容量均不为0。

此时每一次操作的c的和即为最大流。

正确性

从割的角度来证明最大流的正确性。

将原图A中的点分为S1和T1两个点集,S1中含有S点,T1含有T点。A的一种割的大小x就为存在S1和T1,使得S1与T1的并为全集、S1与T1的交为空集且S1与T1之间的所有连边的和为x。

残量网络

上述操作结束后,所有容量不为0的边(注意:是有向的)组成的图C。

根据图C可以求出一个合法的图A的割,且该割的大小就为所有操作的c的和(即流量)

证明:

首先在图C上找到与S联通的点集,即为S1,其余点为T1。

显然S1中一定不会包含T。

记S1与T1之间的边的边集为E。

引理:求最大流过程中所有S->T的路径中不可能会同时经过两条边x,y且x,y均属于E。

采用反证法:如果存在一条路径同时经过两条边x,y且x,y均属于E。

那么这一条路径上的点一定是先属于S1,再属于T1,再属于S1。

如果经过了T1->S1这条边,那么其反向边一定会出现在残量网络中,也就是T1中的某个点其实应该是属于S1的(即与S联通),就与题设不符。

所以E中所有边都会在选出的所有S->T的路径中有且仅出现一次。

所以E就是这个割的集合,且割的大小为E中所有边的大小之和,即所有操作的c的和。

根据图C求出的图A的割的大小是固定的,即为最大流

证明:

假设有两种操作方法使得最后的最大流并不相同。假设第一种操作方法求出的割为E1,第二种操作方法求出的割为E2。

不妨设第一种方法的最大流c1小于第二种c2。

由于E1的割已经限制了网络流的最大流最多为c1,所以与第二种操作方法求出的网络流流量为c2>c1相矛盾。

所以无论从S->T的路径如何选择,按照上述方法最终得到的最大流的大小一定相同,即就是该网络的最大流。

因此这种方法是正确的。

实现方式

本文采用dinic的方法进行实现。

具体方法

朴素的网络流求法的复杂度极高,其瓶颈就在于每一次只能找到一条路径。

但是我们知道很多的路径其实会有很多重复的段,所以我们可以尝试同时找到多条路径来降低复杂度。这就是dinic算法的核心所在。

首先对网络进行bfs分层,记作d数组,(即按照从S出发到每一个点的最少边数进行分类)然后仅保留相邻层之间的边(即x->y存在等价于d(y)=d(x)+1)

这样可以保证求路径的时候不在一个环上打转而陷入死循环,这样也可以让后续对路径的寻找像一棵树一样比较方便。

接着使用dfs的方式来深搜所有可能的路径。一种普遍的方式就是dfs的时候记录当前结点编号和要经过当前结点的路径的c大小之和(即流量的大小之和)。

当前弧优化:如果某个点以后已经不存在到达T的路径了,那么我们就不再去遍历这个点,这个能够保证时间复杂度的正确。

代码:

long long dfs(int x,long long flow){if (x==T) return flow;long long rest=flow;for (int i=1;i<=e_cnt[x];i++){int y=e[x][i].y;if (d[y]==d[x]+1&&v[e[x][i].bh]>0){long long cost=min(v[e[x][i].bh],rest);long long p=dfs(y,cost);if (p==0) d[y]=-1e9;v[e[x][i].bh]-=p;v[e[x][i].bh^1]+=p;rest-=p;if (rest==0) return flow;}}return flow-rest;}

dfs之后我们就再次进行bfs,如此往复,直到dfs之后不再存在从S到T的路径。

整个代码如下:

#include#include#define N 3000001using namespace std;int tot,n,m,S,T;int pd[N],h[N],e_cnt[N],d[N];long long v[N];struct node{int y,bh;};vector<node>e[N];void insert(int x,int y,long long z){tot++;e_cnt[x]++;e[x].resize(e_cnt[x]+1);e[x][e_cnt[x]].y=y;e[x][e_cnt[x]].bh=tot;v[tot]=z;}bool bfs(){for (int i=1;i<=n;i++) d[i]=-1e9;int l=1,r=1;h[l]=S;d[S]=0;while (l<=r){int u=h[l];for (int i=1;i<=e_cnt[u];i++){int y=e[u][i].y;if (d[y]==-1e9&&v[e[u][i].bh]>0){d[y]=d[u]+1;if (y==T) return true;r++;h[r]=y;}}l++;}return false;}long long dfs(int x,long long flow){if (x==T) return flow;long long rest=flow;for (int i=1;i<=e_cnt[x];i++){int y=e[x][i].y;if (d[y]==d[x]+1&&v[e[x][i].bh]>0){long long cost=min(v[e[x][i].bh],rest);long long p=dfs(y,cost);if (p==0) d[y]=-1e9;v[e[x][i].bh]-=p;v[e[x][i].bh^1]+=p;rest-=p;if (rest==0) return flow;}}return flow-rest;}int main(){freopen("maxflow.in","r",stdin);freopen("maxflow.out","w",stdout);scanf("%d%d%d%d",&n,&m,&S,&T);for (int i=1;i<=n;i++){e_cnt[i]=0;e[i].resize(2);}tot=1;for (int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);insert(x,y,z);insert(y,x,0);}long long maxflow=0;while (bfs())maxflow+=dfs(S,1e14);printf("%lld\n",maxflow);}

时间复杂度的计算与证明

第一部分 dfs的时间复杂度

我们知道,只要一次寻找路径是有效的,即找到了至少一条路径,那么就会有至少一条边的容量变为0。

也就是说在拥有当前弧优化的条件下,dfs(k,x)被调用的次数不会超过 |V||E|。所以只要对于每一个点遍历边的时候都使得会有效调用dfs,那么一次dfs的复杂度就会是|V||E|(注:上述代码中dfs的复杂度其实并不正确,但是由于上限十分宽松,没有必要一定要将复杂度写得非常严谨)。

第二部分 bfs的次数

引理:对于所有的结点x,记d(x,y)表示第y次bfs后的层数,有d(x,y)>=d(x,y-1)

证明:对层数进行数归。假设1~t-1层的点都已经满足。

对t+1层的点进行考虑,即假设d(x,p)=t。

任取一条从S->b的路径,

当这条路径上存在a->b,这条边在第p次dfs之后并不存在:

假设a->b是离x最近的一条原先不存在的边。则在d(a,p-1)>=d(b,p-1),且d(a,p)+1=d(b,p)

由于b->x在上一次的图中仍然存在,所以有d(b,p-1)+len(b,p)>=d(x,p-1)。

由于d(x,p)=d(a,p)+len(b,p)+1且d(a,p)>=d(a,p-1)>=d(b,p-1),所以d(x,p)>=d(b,p-1)+len(b,p)+1,即d(x,p)>d(x,p-1)。

而当不存在a->b的时候,有d(x,p)=d(x,p-1)。

综上,有d(x,y)>=d(x,y-1)。

而每一次dfs之后保留原先存在的边之后S与T不再联通,所以从S到T的最短路径上一定存在原先并不存在的边。所以d(T,y)>d(T,y-1)。

而d(T,y)<=|V|恒成立。所以bfs的次数最多为|V|。

因此总时间复杂度为|V|^2*|E|。

但是很难将这种方法卡到复杂度的上界,所以它跑大部分的规模是10^5的图都是绰绰有余的。

来源地址:https://blog.csdn.net/sulvshuo/article/details/131491835

--结束END--

本文标题: 网络流算法

本文链接: https://www.lsjlt.com/news/393645.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • 网络流算法
    网络流 最大流的求法 我们对原图的每一条边再存储一条反向边,形成一个含有反向边的新图B。 起初反向边的容量为0,正向边的容量为原图中的容量。 每一次在图B上寻找一条从S->T的路径(注:该路径也就是增...
    99+
    2023-09-04
    算法
  • 网络作业11【计算机网络】
    网络作业11【计算机网络】 前言推荐网络作业11一. 单选题(共22题,88分)二. 填空题(共1题,10分)三. 多选题(共1题,2分) 最后 前言 2023-6-29 17:27:...
    99+
    2023-09-03
    网络 计算机网络 php
  • python网络-计算机网络基础(23)
    一、网络简介 网络是由节点和连线构成,表示诸多对象及其相互联系。 一个人玩:   两个人玩:   多个人玩: 说明 网络就是一种辅助双方或者多方能够连接在一起的工具 如果没有网络可想单机的世界是多么的孤单 使用网络的目的 就是...
    99+
    2023-01-31
    计算机网络 基础 网络
  • 计算机网络之一:网络架构
    一:七层架构OSI是Open System Interconnect即开放系统互连模型。二:五层架构三:四层架构TCP/IP四层模型四层协议和对应的标准七层协议的关系如下图:四:数据包五:程序是如何工作的...
    99+
    2023-06-03
  • Linux 网络发包流程
    哈喽大家好,我是咸鱼 之前咸鱼在《Linux 网络收包流程》一文中介绍了 Linux 是如何实现网络接收数据包的 简单回顾一下: 数据到达网卡之后,网卡通过 DMA 将数据放到内存分配好的一块 rin...
    99+
    2023-08-30
    linux 网络 运维
  • 计算机网络(2) --- 网络套接字UDP
    计算机网络(1) --- 网络介绍_哈里沃克的博客-CSDN博客https://blog.csdn.net/m0_63488627/article/details/131967378spm=1001.2014.3001.5501 目录 1....
    99+
    2023-10-02
    计算机网络 linux c++ 网络
  • 【计算机网络】Linux 内核网络概述
     文章目的 了解 Linux 内核网络架构通过网络包过滤器或者防火墙获得使用的 IP 数据包(分组)管理技巧熟悉如何在 Linux 内核级别使用套接字 概述         网络应用程序的开发过去这些年按照指数级增长,这样增加了对系统网络子...
    99+
    2023-10-04
    linux 内核套接字 socket
  • 计算机网络中平板无法加入无线网络的解决方法
    这篇文章主要介绍计算机网络中平板无法加入无线网络的解决方法,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!平板无法加入无线网络的解决方法:1、打开设置,进入通用栏目;2、找到并点击还原选项,点击还原网络设置;3、在弹出...
    99+
    2023-06-06
  • 网络数据加密算法有哪些
    常见的网络数据加密算法有以下几种AES加密算法AES算法是基于排列和置换运算实现的,排列是对数据重新进行安排,置换是将一个数据单元替换为另一个,AES是一个迭代的、对称密钥分组的密码,是使用相同的密钥进行加密和解密数据的。RSA加密算法RS...
    99+
    2024-04-02
  • matlab神经网络算法怎么实现
    在MATLAB中,可以使用神经网络工具箱来实现神经网络算法。以下是一个简单的例子,展示了如何使用MATLAB实现一个简单的前馈神经网...
    99+
    2023-10-12
    matlab
  • 计算机网络-计算机网络体系结构-物理层
    目录 一、通信基础 通信方式 传输方式 码元 传输率 *二 准则 2.1奈氏准则(奈奎斯特定理) 2.2香农定理 三、信号的编码和调制 *数字数据->数字信号 数字数据->模拟信号 模拟数据->数字信号 模拟数据->模拟信号 *四、数据交换...
    99+
    2023-10-07
    计算机网络 笔记
  • 计算机网络默认网关如何算
    这篇文章主要介绍了计算机网络默认网关如何算的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇计算机网络默认网关如何算文章都会有所收获,下面我们一起来看看吧。如何算默认网关 首先要铺垫一些基础知识,整个互联网就是一个...
    99+
    2023-07-01
  • 【计算机网络】简易TCP网络小程序
    文章目录 1. 简易TCP网络程序1.1 服务端1.1.1 服务端创建套接字1.1.2 服务端绑定1.1.3 服务端监听1.1.4 服务端获取连接1.1.5 服务端处理请求 1.2 客户...
    99+
    2023-09-02
    网络 计算机网络 tcp/ip
  • 【网络】计算机网络基础概念入门
    🍁 博主 "开着拖拉机回家"带您 Go to New World.✨🍁 🦄 个人主页——🎐个人主页 🎐✨🍁 🪁...
    99+
    2023-10-19
    计算机网络 OSI网络模型 TCP/IP模型 MAC帧地址 套接字 虚拟网络互联 网络分类
  • win8系统如何可以查看无线网络流量?win8查看无线网络流量的方法
      win8查看无线网络流量的方法:   1、打开电脑之后,左键单击桌面右下方的那个信号图标;   2、单击一下win8系统下面的无线信号小图标就会跳出选择;   3、点击已连接好的无线信号,然后就会跳...
    99+
    2022-06-04
    无线网络 流量 可以查看
  • 计算机网络速成
    更好的阅读体验 \color{red}{\huge{更好的阅读体验}} 更好的阅读体验 因特网...
    99+
    2023-09-09
    计算机网络 网络
  • 计算机网络概述
    目录 一、计算机网络的作用及互联网概述 1.1计算机网络在信息时代中的作用 1.2基本概念 1.3互联网基础架构发展三个阶段 1.4互联网的标准化工作 二、互联网的组成 2.1互联网组成 2.2互联网的边缘部分 2.3互联网的核心部分 三...
    99+
    2023-10-24
    计算机网络 网络
  • 计算机网络实验
    一、验证性实验 1. ipconfig 自己计算机网络配置 ipconfig /all ​ 物理地址. . . . . . . . . . . . . : 00-E0-4C-68-04-91 IPv4 地址 . . ...
    99+
    2023-10-20
    网络 网络协议 服务器 Powered by 金山文档
  • 计算机网络中网站死链的处理方法
    这篇文章主要介绍计算机网络中网站死链的处理方法,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!在网站日常SEO优化运营过程中,运营者难免会遇到各种问题,其中,死链就是其中之一。死链的产生,对于网站在搜索引擎中的收录是不...
    99+
    2023-06-10
  • 神经网络——Python实现BP神经网络算法(理论+例子+程序)
    一、基于BP算法的多层感知器模型 采用BP算法的多层感知器是至今为止应用最广泛的神经网络,在多层感知器的应用中,以图3-15所示的单隐层网络的应用最为普遍。一般习惯将单隐层前馈网称为三层感知器,所谓三层包括了输入层、隐层和输出层。 算法...
    99+
    2023-08-31
    神经网络 算法 python 深度学习
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作