国家集训队2007论文集7.胡伯涛《最小割模型.ppt
《国家集训队2007论文集7.胡伯涛《最小割模型.ppt》由会员分享,可在线阅读,更多相关《国家集训队2007论文集7.胡伯涛《最小割模型.ppt(43页珍藏版)》请在三一文库上搜索。
1、最小割模型 在信息学竞赛中的应用 Applications of Minimum Cut Model in Informatics,胡伯涛 Amber ADN.cn 福州第一中学 Fuzhou No.1 Middle School,最小割定义,网络的割S,T 将点集V划分为S和T两部分,(其中源s属于S且汇t属于T),而从S指向T的边组成割 割容量 割中所有边的容量和 最小割 容量最小的割,1,2,3,4,t,s,最小割解法,最大流最小割定理 网络的最大流流值该网络的最小割容量 求解最小割的有力武器 记 表示在点数为n,边数为m的网络中求最大流,两个部分 最大权闭合图 标准解答的一个更一般化的
2、扩展模型 改进算法 达到用最大流解决该问题的理论下界,引入,NOI 2006 最大获利 最小割是最大流的对偶问题。 不直观,模型隐蔽。 展示最小割模型应用的巧妙构图方法和独特思维方式,网络流首次进入NOI,NOI 2006 最大获利 (Profit) 问题描述,简要描述 有n个结点,m条无向边可供建设。 建立一个结点u有一定的花费pu。建立一条无向边有一定的非负收益we。 建立一条无向边(u, v)的必要条件是要先建立点u,点v。 求最大获利。,NOI 2006 最大获利 (Profit) 分析,目的:选出一个边集E, 点集V。且最大化: 限制条件:对于在E中每条边(u, v),它的端点u,v
3、一定要在V中。 提出解决事件依赖关系的有力图论工具:闭合图。,必要条件,边,依赖,点,最大权闭合图 定义,有向图的闭合图(closure): 闭合图内任意点的任意后继也一定还在闭合图中。 物理意义 事物间依赖关系:一个事件要发生,它需要的所有前提也都一定要发生。 最大权闭合图是点权之和最大的闭合图。,其中3, 4, 5是一个闭合图。3的后继4,4的后继5,都在闭合图中。,1,2,3,4,5,5,-6,7,0,-3,而1, 4, 5不是一个闭合图,因为点2是点1的后继,但不在闭合图中。,最大权闭合图 解决,复杂度为,解法略去,最大权闭合图 构图,增加源s汇t 源s连接原图的正权点,容量为相应点权
4、 原图的负权点连接汇t,容量为相应点权的相反数 原图边的容量为正无限.,1,2,3,4,5,5,-6,7,0,-3,s,t,6,3,最大权闭合图 解决,复杂度为,闭合图方案V与不含正无限容量的割S, T一一对应,闭合图V的权为正权点总和减去对应割的容量,割S, T取最小时,闭合图权取最大。,NOI 2006 最大获利 (Profit) 标准算法,将原题中的边和点都看成事件。边事件依赖边的两个端点事件的发生。这与闭合图的性质相似。 构造性地,将边转化为点事件。,2,1,e,NOI 2006 最大获利 (Profit) 标准算法,将所有边都转化为事件点,原图便转化为一个二分图。这样新构造的二分图的
5、闭合图就对应了原问题的一个解。解决该二分图的最大权闭合图即可,4,1,3,2,e1,e2,e3,e4,1,2,3,4,e1,e2,e3,e4,转二分图,复杂度为,最大权闭合图 小结,在任意带权有向图中,只要有依赖关系需要解决,最大权闭合图都普遍适用。(普适性) 在最大获利的解决方法1中,最大权闭合图来解决二分图模型。(特殊性),牛刀宰鸡,对症下药,改进算法 提出,必要条件,边,依赖,点,充分条件,边,创建,点,正向思维(被动),逆向思维(主动),重定义 两个端点都在点集V里的所有边组成了边集E 即V的导出子图。,V间的边E 与V关联的所有边 V与V补集之间的边,改进算法 分析,先选点集V 再找
6、V之间的边集E,1,3,4,2,8,7,6,5,圈内的点组成V 蓝边组成E 红边组成V与V补集之间的边,?,补集转化 再次逆向思维,V,E,割,最小割,最大化,改进算法 尝试构图,选出点集V 对于每个点:选或不选 构图 从源向每个点连边 从每个点向汇连边,1,2,s,t,V,对于每个点,割必会割断它到源或它到汇的两条边中的一条 不妨设,到汇的边被割断的点组成V 则V中每个点连接汇的边都在割内 选入V的点的一些代价信息,可以加载到这条被割掉的边上。,V间的边E 与V关联的所有边 V与V补集之间的边,V间的边E (V与V补集之间的边V关联的所有边),改进算法 分析,v,3,2,V,4,5,凑入最小
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 国家 集训队 2007 论文集 胡伯涛 最小 模型
链接地址:https://www.31doc.com/p-2094173.html