网络流最大流 Dinic算法

2024-01-03 14:39
文章标签 算法 最大 网络 dinic

本文主要是介绍网络流最大流 Dinic算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

O(N^2*M)的算法
比EK的O(N*M^2)优很多
EK通常解决10^3 –10^4规模的网络
而dinic能解决10^4–10^5的网络

Dinic算法的思想也是分阶段地在层次网络中增广。它与最短增广路算法不同之处是:最短增广路每个阶段执行完一次BFS增广后,要重新启动BFS从源点Vs开始寻找另一条增广路;而在Dinic算法中,只需一次DFS过程就可以实现多次增广,这是Dinic算法的巧妙之处。Dinic算法具体步骤如下:

(1)初始化容量网络和网络流。

(2)构造残留网络和层次网络,若汇点不再层次网络中,则算法结束。

(3)在层次网络中用一次DFS过程进行增广,DFS执行完毕,该阶段的增广也执行完毕。

(4)转步骤(2)。

贴模板:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring> 
#include<cmath>
#define N 10005
#define M 200005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,s,t,cnt=1,head[N],incf[N],d[N],maxflow; struct Node{int to,nxt,val;
}edge[M];void add(int x,int y,int z)
{cnt++;edge[cnt].to=y;edge[cnt].nxt=head[x];edge[cnt].val=z;head[x]=cnt;
}bool bfs()
{memset(d,0,sizeof d);queue<int> q;q.push(s);  d[s]=1;while(q.size()){int u=q.front(); q.pop();for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(edge[i].val && !d[v]){q.push(v);d[v]=d[u]+1;if(v==t) return true;}}}return false;
}int dinic(int x,int flow)
{if(x==t) return flow;int res=flow,k;for(int i=head[x];i && res;i=edge[i].nxt){int v=edge[i].to;if(edge[i].val && d[v]==d[x]+1){k=dinic(v,min(res,edge[i].val));if(!k) d[v]=0;  //剪枝,去掉增广完毕的点edge[i].val-=k;edge[i^1].val+=k;res-=k;}}return flow-res;
}int main()
{scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z); add(y,x,0);//成对储存 }int flow=0;while(bfs()){while(flow=dinic(s,inf)) maxflow+=flow;}printf("%d",maxflow);return 0;
}

这篇关于网络流最大流 Dinic算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/566035

相关文章

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压:数据存储与传输的优化核心1. zip/unzip:通用压缩格式的便捷操作2.

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Linux网络配置之网桥和虚拟网络的配置指南

《Linux网络配置之网桥和虚拟网络的配置指南》这篇文章主要为大家详细介绍了Linux中配置网桥和虚拟网络的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、网桥的配置在linux系统中配置一个新的网桥主要涉及以下几个步骤:1.为yum仓库做准备,安装组件epel-re

python如何下载网络文件到本地指定文件夹

《python如何下载网络文件到本地指定文件夹》这篇文章主要为大家详细介绍了python如何实现下载网络文件到本地指定文件夹,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...  在python中下载文件到本地指定文件夹可以通过以下步骤实现,使用requests库处理HTTP请求,并结合o

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n