没有合适的资源？快使用搜索试试~
我知道了~
首页
最大流DInic算法(链式前向星)
最大流DInic算法(链式前向星)
最大流
可行流
链式前向星
网络流
需积分: 47
366 浏览量
更新于2023-05-25
评论
收藏
324KB
PPT
举报
立即下载
开通VIP（低至0.43/天）
送1年+限时优惠
身份认证 购VIP最低享 7 折!
领优惠券(最高得80元）
给师弟师妹们讲网络流Dinic算法与可行流用到的讲义，感觉还是不错，分享一下~
资源详情
资源评论
资源推荐
网络流之最大流
•
最大流
Dinic
算法
•
在一个有向图
上选择一个
源点
，一个
汇点
，
每一
条边上都有一
个
流量上限
（以下
称为容量），即
经过这条边的
流量不能超过这个
上界，同时，除
源点和汇点外
，所有点的入流和
出流都相等，而
源点只有流出
的流，汇点只有汇
入的流。这样的
图叫做网络流
。
网络流之最大流
•
Dinic
算法是用来求取这个网络流中最
大流
的算法
•
在此之前你需要熟练掌
握链式前向星建图
链式前向星
•
主要用于存储离散的边
的信息，通过一条
链和链上的
m
个节点将各个边的关系链接
起来；
m
是边的个数
struct node{
int pre;//
表示前一个边
int to,cost;
//
边的指向节点和边权
}e[maxm<<1];
int id[maxn],cnt;//id
始终表示建图后节点所存储的最后一条边，
cnt
是链上节点的个
数
void add(i
nt from,int to,int cost)
{
e[cnt].to =
to;
e[cnt].cost =
cost;
e[cnt].pre =
id[from];
id[from] =
cnt++;
}
void init(){
memset(id,-1,sizeof(id));
cnt =
0;
}
网络流之最大流
•
算法流程
•
BFS
进行
网络流分层处理
•
DFS
寻
找增广路并进行边权的维护
具体就是对于每一个点，我们根据从源点开始的
bfs
序列，为每一个点分配一个深
度，然后我们进行若干遍
dfs
寻找增广路，每一次由
u
推出
v
必须保证
v
的深度必
须是
u
的深度
+1
。
增广路：
1.
找到一条从源点到汇点的路径，使得路径上任意一条边的残量
>0
（注意是小于而
不是小于等于，这意味着这条边还可以分配流量），这条路径便称为增广路
剩余24页未读，
继续阅读
评论0
去评论
C 代码 计算权重函数 rho（x） 的高斯正交规则 基于只需要知识的戈鲁布-韦尔施程序 的时刻 rho（x）.rar
C实用代码
C 代码 将 Atbash 替换密码应用于文本字符串.rar
C语言实现的功能，金品源码
阿里云 专有云企业版 V3.6.0 云数据库OceanBase版 开发指南 - 20180824.pdf
阿里云 专有云企业版 V3.6.0 云数据库OceanBase版 开发指南 - 20180824.pdf
阿里云 专有云企业版 V3.5.2 分布式任务调度SchedulerX 开发指南 - 20180831.pdf
阿里云 专有云企业版 V3.5.2 分布式任务调度SchedulerX 开发指南 - 20180831.pdf
阿里云 专有云企业版 V3.5.2 负载均衡SLB 开发指南 - 20190326.pdf
阿里云 专有云企业版 V3.5.2 负载均衡SLB 开发指南 - 20190326.pdf
C 代码 计算并写出 用于近似积分的高斯-拉盖尔正交规则 密度 exp（-x） 在区间 [0，+oo） 上的函数.rar
实用C代码
深度学习领域5种算法模型ConvNet、InceptionV3、MobileNet、DenseNet、VGG19口罩检测
深度学习领域5种算法模型ConvNet、InceptionV3、MobileNet、DenseNet、VGG19目标检测口罩检测，用于口罩面部识别。包含源码和数据集，python语言，可以作为参考。主页有更多源码。
移动端.pcbdoc
移动端.pcbdoc
C盘，D盘，E盘...序列号更改
hwid
wordgo.jar 解决1.0版本异常报错：创建项目时读写临时文件失败
java word写入poi比较繁琐。wordgo快捷明了，轻量化处理word写入非常方便 WordGo1.0版本部署环境下异常：创建项目时读写临时文件失败 pom.xml meavn <dependency> <groupId>com.github.qrpcode</groupId> <artifactId>wordgo</artifactId> <version>2.0</versio
C 代码 返回任何单项式积分的精确值 在 M 维单位超球体的表面上.rar
实用C代码
C 代码 使用 沃克采样.rar
实用的C语言实现代码
jdk-8u371-windows-x64.exe
解压到当前文件夹
C 代码 使用高斯-勒让德正交估计柯西主值 （CPV）的某些奇异积分.rar
实用的C语言实现代码
C 代码 使用范德蒙德计算二维正交规则的权重 矩阵，假设已指定点.rar
C实用代码
C 代码 显示如何在任何点插值顶点数据 在三角形的内部.rar
C实用代码
EtherCAT主站芯片（ECM-XF）数据手册+参考原理图+使用说明
EtherCAT主站芯片（ECM-XF）数据手册+参考原理图+使用说明 要想自己打板玩一玩Ethercat的老哥们往这里看
异步二－十进制计数器.zip
异步二－十进制计数器
matlab资源 基于MATLAB的药物消费数据集数据探索、特征选择 仅供学习参考用代码.rar
matlab资源 基于MATLAB的药物消费数据集数据探索、特征选择 仅供学习参考用代码
C 代码 解决时间依赖性的捕食者-猎物系统 常微分方程 （ODE）.rar
C实用代码
Df_cjc
粉丝: 15
资源:
1
私信
上传资源 快速赚钱
我的内容管理
收起
我的资源
快来上传第一个资源
我的收益
登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏
我的下载
下载帮助
会员权益专享
图片转文字
PDF转文字
PDF转Word
PDF加水印
全年可省5，000元
立即开通
最新资源
MPC5744P-DEV-KIT-REVE-QSG.pdf
通信原理课程设计报告（ASK FSK PSK Matlab仿真--数字调制技术的仿真实现及性能研究）
一种简单有效的锂电池充电均衡电路.pdf
ABB机器人保养总结解析.ppt
xxx集团信息化建设规划方案 v2.0.docx
储能EMS能量管理系统(1).pdf
如何从 Java 存储过程将 JDBC ResultSet 作为 Ref Cursor 返回.doc
RS-232接口电路的ESD保护.pdf
ISO20000-1-2018版-CN中英文-一丁.pdf
YRC1000 DeviceNet传输功能说明书.pdf
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
安全验证
文档复制为VIP权益，开通VIP直接复制
信息提交成功
评论0