转自 Good morning 的几句精辟的话
2024-08-20 23:28:04
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.小结
网络流的本质其实就是贪心
网络流和不等式,流量平衡方程密不可分,在某种意义上,他们甚至可以说是等价的
网络流往往能处理一些依赖关系非常强的最优化问题
网络流的一些经典模型要熟悉,如最大权闭合图一类的最小割模型的应用,平面图网络流转最短路(反过来也不无可能的说)
如果要用网络流来搞题目,一定要列出目标式,明确要最优化的方向,通过对式子的变形来让看起来没法做的变得可以做;或是直接列流量平衡方程来构图
费用流相当于是给最大流增了一维,功能更强大的代价是速度慢了
最新文章
- WMI
- RSA算法原理(一)
- oracle 使用基本问题
- Hibernate中为什么要重写equals方法和hashcode方法
- RobotFramework安装完成后怎么在桌面显示ride图标
- quartz定时格式配置以及JS验证
- MyEclipse中设置注释模板的方法
- Setting up Latex-vim (or Latex-suite) plugin within macVim under Mac OSX Yosemite 2015-1-20 by congliu
- simple_list_item_1 和simple_list_item_2有什么区别???
- 关于mysql存储过程中传decimal值会自动四舍五入的这个坑
- GO语言的进阶之路-面向对象编程
- 转:【WebView的cookie机制 】轻松搞定WebView cookie同步问题
- angularjs启动项目报ERROR in AppModule is not an NgModule解决方法
- jq塞入不同状态html的写法 switch (defaults.type)
- centos yum 安装php mysql
- cocos2dx中使用tolua++使lua调用c++函数
- Java敲地鼠代码
- vue cli3超详细创建多页面配置
- HDU 1114 Piggy-Bank (dp)
- import方法引入模块详解
热门文章
- (poj)3020 Antenna Placement 匹配
- Openjudge/Poj 1183 反正切函数的应用
- 解决:error: &#39;Can&#39;t connect to local MySQL server through socket &#39;/var/run/mysqld/mysqld.sock&#39; (2)&#39;
- BootstrapDialog.show函数底层简化
- Python3 正则表达式
- think完全还原原形的 SQL
- cgi创建web应用(一)之传递表单数据与返回html
- 解决laravel中环境配置不起作用的方法
- Dede 列表页 缩略图 有显示无则不显示
- 1-了解Python