没有合适的资源?快使用搜索试试~ 我知道了~
首页7[1].胡伯涛《最小割模型在信息学竞赛中的应用》
资源详情
资源评论
资源推荐
最小割模型
在信息学竞赛中的应用
Applications of Minimum Cut Mod
el
in Informatics
胡伯涛 Amber
[ADN.cn]
福州第一中学 Fuzhou No.1 Middle School
▪
两个部分
1.最大权闭合图
标准解答的一个更一般化的扩展模型
2.改进算法
达到用最大流解决该问题的理论下界
引入
NOI 2006 最大获利
▪
最小割是最大流的对偶问题。
不直观,模型隐蔽。
▪
展示最小割模型应用的巧妙构图方法和独
特思维方式
网络流首次进入 NOI
NOI 2006 最大获利 (Profit)
问题描述
简要描述
▪
有 n 个结点, m 条无向边可供建设。
▪
建立一个结点 u 有一定的花费 p
u
。建立一
条无向边有一定的非负收益 w
e 。
▪
建立一条无向边 (u, v ) 的必要条件是要先建
立点 u ,点 v 。
▪
求最大获利。
NOI 2006 最大获利 (Profit)
分析
▪
目的:选出一个边集 E’, 点集 V’ 。且最大
化:
▪
限制条件:对于在 E’ 中每条边 (u, v) ,它的
端点 u , v 一定要在 V’ 中。
提出解决事件依赖关系的有力图论工具:闭合图。
必要条件
' '
Maximize
e v
e E v V
w p
边
依赖
点
最大权闭合图
定义
▪
有向图的闭合图( clos
ure ):
闭合图内任意点的任意
后继也一定还在闭合图
中。
▪
物理意义
事物间依赖关系:一个事
件要发生,它需要的所有
前提也都一定要发生。
▪
最大权闭合图是点权之
和最大的闭合图。
其中 {3, 4, 5} 是一个闭合图。 3 的
后继 4 , 4 的后继 5 ,都在闭合图
中。
1 2
3 4
5
5
-6
7
0
-3
而 {1, 4, 5} 不是一个闭合图,因为
点 2 是点 1 的后继,但不在闭合图
中。
剩余36页未读,继续阅读
lz9506
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论1