首页 技术 正文
技术 2022年11月10日
0 收藏 458 点赞 2,752 浏览 603 个字

1.志愿者招募

根据流量平衡方程来构图非常方便,而且简单易懂,以后可能成为做网络流的神法之一

简单记一下流量平衡方程构图法的步骤:

a.列出需求不等式

b.通过设置松弛变量,将不等式变成等式

c.两两相减,得到流量平衡方程

d.观察方程,>0表示得到的流量,<0表示输出的流量,如果是跟需求量有关的变量,则跟源点和汇点连,如果是跟费用有关的变量则把相关的方程对应连边

e.使用最小费用最大流算法求解

具体连边方法:令oo=maxlongint,连(i,j,k,l)表示i向j连容量为k,费用为l的边

a.令a[0]=a[n+1]=0,对于a[i]-a[i-1]>0连(s,i,a[i]-a[i-1],0),而a[i]-a[i-1]<0,则连(i,t,a[i-1]-a[i],0)

b.连(i+1,i,oo,0)

c.对于每类志愿者(x,y,z),连(x,y+1,oo,z)

2.小结

网络流的本质其实就是贪心

网络流和不等式,流量平衡方程密不可分,在某种意义上,他们甚至可以说是等价的

网络流往往能处理一些依赖关系非常强的最优化问题

网络流的一些经典模型要熟悉,如最大权闭合图一类的最小割模型的应用,平面图网络流转最短路(反过来也不无可能的说)

如果要用网络流来搞题目,一定要列出目标式,明确要最优化的方向,通过对式子的变形来让看起来没法做的变得可以做;或是直接列流量平衡方程来构图

费用流相当于是给最大流增了一维,功能更强大的代价是速度慢了

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,022
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,513
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,359
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,142
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,773
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,851