《最小割模型在信息学竞赛中的应用》由会员分享，可在线阅读，更多相关《最小割模型在信息学竞赛中的应用（37页珍藏版）》请在金锄头文库上搜索。
1、最小割模型 在信息学竞赛中的应用最小割定义 网络的割S,T 将点集V划分为S和 T两部分，(其中源s属于S且汇t属于T)， 而从S指向T的边组成割 割容量 割中所有边的容量和 最小割 容量最小的割1234ts最小割解法 最大流最小割定理 网络的最大流流值该网络的最小割容量 求解最小割的有力武器 记表示在点数为n，边数为m的网络中求最大 流 两个部分 1.最大权闭合图 标准解答的一个更一般化的扩展模型 2.改进算法 达到用最大流解决该问题的理论下界 引入NOI 2006 最大获利 最小割是最大流的对偶问题。 不直观，模型隐蔽。 展示最小割模型应用的巧妙构图方法和独 特思维方式网络流首次进入NOI
2、NOI 2006 最大获利 (Profit) 问题描述简要描述 有n个结点，m条无向边可供建设。 建立一个结点u有一定的花费pu。建立一条 无向边有一定的非负收益we。 建立一条无向边(u, v)的必要条件是要先建 立点u，点v。 求最大获利。NOI 2006 最大获利 (Profit) 分析 目的：选出一个边集E, 点集V。且最大化 ： 限制条件：对于在E中每条边(u, v)，它的 端点u，v一定要在V中。提出解决事件依赖关系的有力图论工具：闭合图。必要条件边依赖点最大权闭合图 定义 有向图的闭合图（ closure）： 闭合图内任意点的任意 后继也一定还在闭合图 中。 物理意义 事物间依赖
3、关系：一个事 件要发生，它需要的所有 前提也都一定要发生。 最大权闭合图是点权之 和最大的闭合图。其中3, 4, 5是一个闭合图。3的后 继4，4的后继5，都在闭合图中。123455-670-3而1, 4, 5不是一个闭合图，因为 点2是点1的后继，但不在闭合图 中。最大权闭合图 解决复杂度为解法略去最大权闭合图 构图1. 增加源s汇t 2. 源s连接原图的正权点，容量为相应点权 3. 原图的负权点连接汇t，容量为相应点权的相反数 4. 原图边的容量为正无限. 123455-670-3st63最大权闭合图 解决复杂度为闭合图方案V与不含正无限容量的割S, T一一对应闭合图V的权为正权点总和减去
4、对应割的容量割S, T取最小时，闭合图权取最大。NOI 2006 最大获利 (Profit) 标准算法 将原题中的边和点都看成事件。边事件依 赖边的两个端点事件的发生。这与闭合图 的性质相似。 构造性地，将边转化为点事件。e21eNOI 2006 最大获利 (Profit) 标准算法 将所有边都转化为事件点，原图便转化为一个二分 图。这样新构造的二分图的闭合图就对应了原问题 的一个解。解决该二分图的最大权闭合图即可4132e1e2e3e41234e1e2e3e4转二分图复杂度为最大权闭合图 小结 在任意带权有向图中，只要有依赖关系需 要解决，最大权闭合图都普遍适用。（普 适性） 在最大获利的解
5、决方法1中，最大权闭合图 来解决二分图模型。（特殊性）牛刀宰鸡对症下药改进算法 提出必要条件边依赖点充分条件边创建点正向思维（被动）逆向思维（主动）重定义 两个端点都在点集V里的所有边组成了边集E 即V的导出子图。V间的边E 与V关联的所有边 V与V补集之间的边改进算法 分析 先选点集V 再找V之间的边集E13428 765圈内的点组成V 蓝边组成E 红边组成V与V补集之间的边?补集转化 再次逆向思维VE割最小割最大化改进算法 尝试构图 选出点集V 对于每个点：选或 不选 构图 从源向每个点连边 从每个点向汇连边12stV 对于每个点，割必会割 断它到源或它到汇的两 条边中的一条 不妨设，到汇
6、的边被割 断的点组成V则V中每个点连接汇的边都 在割内 选入V的点的一些代价信息 ，可以加载到这条被割掉的 边上。V间的边E 与V关联的所有边 V与V补集之间的边V间的边E (V与V补集之间的边 V关联的所有边)改进算法 分析v32V45凑入最小割微观地，考察单独的在V中点v 与v关联所有E内的边 = （与v关联所有割边 与v关联所有边） 令 表示与点v关联的 总边权和vst 每个点到汇的边 容量为V间的边E V的点权 (V与V补集之间的边与V关联的所有边 V的点权)V间的边E (V与V补集之间的边与V关联的所有边) 由于最小割算法只能处理非负边权，故在每条边 的容量加上一个足够大的数U即可。
7、改进算法 构图12st 每个点向汇连的边的容 量为 考虑点权： 每个点到汇的边容量增 加该点点权的两倍 最后，保留原图的边，容量即为原边权。凑入最小割改进算法 解决 通过以上公式变形，可知答案为 其中cS,T为最小割，证明从略复杂度为改进算法 对比最大权闭合图改进算法点数n边数0.71s40.41sn+mn+mn+m实际效果改进算法 小结改进动机利用最小割的想法不断的完善这个想法得出极为精妙的构造两次逆向思维微观的观察分别将边权，点权因素凑入最小割数学美论文特点 研究的重点是最小割模型的应用 不仅仅给出了结论，还着重阐述得出结论 的分析过程。 不仅授之以鱼，还授之以渔。 分析过程，是以Poly
8、a在数学思想方法论中 的精华怎样解题表作为贯串思维 的主线。如刚才的构造过程就充分的展示 了这一特点。论文研究内容主要研究四个方面的应用 基于最小割定义的直接应用 最大权闭合图 最大密度子图 二分图的最小点权覆盖集与最大点权独立 集 刚才所谈的例题最大获利便涉及了最大权闭合图，最大密度子图这 两个方面的内容。 其中改进算法可以作为求解最大密度子图的一个子过程。论文研究内容 Sorry for poor time.感谢感谢越南的Thanh Vy 感谢郭华阳提供原创题 感谢王欣上的测试实验感谢CCF提供给我一个展示自我的舞 台谢谢大家 Thanks to you allAmber ADN.cn 改
9、进算法证明关于实现效率 本人实现的Preflow Push 40.41s 0.71s 王欣上提供的Dinic测试： 1.7s 0.3s总结转化过程的模式 Transforming Pattern 建立一一对应关系 割的性质 Property of Cut 不存在任何一条s到t的路径 将点集分成两类 技巧 用正无限的容量排除不参与决策的边 使用割的定义式来分析最优性 利用与源或汇关联的边容量处理点权最大权闭合图 证明 该通过对以上网络的最小割的求解，可以 得到原问题的解。 概念：若一个割不包含正无限容量的边， 称该割为简单割。最小割必是简单割。 闭合图V1与简单割S, T间有一一对应关系因为在简
10、单割中，S到T间的边都不是正无限容量的边 ，即都不是原图的边。故一一对应关系成立。最大权闭合图 证明由最小割的定义，有：所以得到：式(1)最大权闭合图 证明又由闭合图的定义，得到：式(2)将式(1)与式(2)加起来，得到：总复杂度为最大密度子图 定义 定义一个无向图的密 度(density)为该图的 边数与该图的点数的 比值 最大密度子图是一个 具有最大密度的子图 由于目标是求最大, 可以 直接把子图重定义为的子 图点集的导出子图其中在虚线内的点与边组成最大密 度子图，密度为 5/4最大密度子图 主算法 这是0-1分数规划的模型 对答案值的二分查找，将分数规划转化为一般规 划 对于一个答案的猜
11、测值g，新函数 形式化地重新叙述本模型 最大密度子图 主算法 性质: 1. 具有单调性; 2.又根据Dinkelbach 定理, 函数图像与x轴的交点, 即为目标解. 对答案进行二分查找. 设二分查找的次数为 k, 则总复杂度为最大密度子图 初步算法 基本的限制条件: 边(u, v)存在于子图中的必要条件 为点u, v也存在于子图中. 根据这必要条件的关系, 想到使用最大权闭合图的 方法解决. 依然是将边看成点即可. 复杂度为需要改进！最大密度子图 改进算法（1）2最大密度子图 改进算法 将上面的思路整理一下 在原图点集的基础上增加源和汇；将每条原无向边替换为 两条容量为1的有向边；连接源s到每个点，容量为U；连 接汇t到每个点，容量为U+2g-dv。 U为一个足够大的数。最大密度子图 改进算法改进算法证明复杂度为推广1：改进算法的点权和边权推广 定义带边权无向图的密度为该图的边权和与该图 的点数的比值:推广2：改进算法的点权和边权推广 定义点边均带权的无向图的密度为该图的点权和加 上边权和的和与该图的点数的比值，即重新解决 NOI 2006 最大获利 (Profit)点有权，边也有权。想到可以利用推广2来解 决. 复杂度为
