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