7.胡伯涛《最小割模型在信息学竞赛中的应用》.ppt

最小割模型在信息学竞赛中的应用ApplicationsofMinimumCutModelinInformatics胡伯涛Amber[]《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》最小割定义网络的割[S,T]——将点集V划分为S和T两部分,(其中源s属于S且汇t属于T),而从S指向T的边组成割割容量——割中所有边的容量和最小割——《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》最小割解法最大流最小割定理网络的最大流流值=该网络的最小割容量求解最小割的有力武器记 表示在点数为n,《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》两个部分最大权闭合图标准解答的一个更一般化的扩展模型改进算法达到用最大流解决该问题的理论下界引入NOI2006最大获利最小割是最大流的对偶问题。不直观,模型隐蔽。《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》NOI2006最大获利(Profit)问题描述简要描述有n个结点,m条无向边可供建设。建立一个结点u有一定的花费pu。建立一条无向边有一定的非负收益we。建立一条无向边(u,v)的必要条件是要先建立点u,点v。求最大获利。《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》NOI2006最大获利(Profit)分析目的:选出一个边集E’,点集V’。且最大化:限制条件:对于在E’中每条边(u,v),它的端点u,v一定要在V’中。提出解决事件依赖关系的有力图论工具:闭合图。《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》最大权闭合图定义有向图的闭合图(closure):闭合图内任意点的任意后继也一定还在闭合图中。物理意义事物间依赖关系:一个事件要发生,它需要的所有前提也都一定要发生。最大权闭合图是点权之和最大的闭合图。其中{3,4,5}是一个闭合图。3的后继4,4的后继5,都在闭合图中。123455-670-3而{1,4,5}不是一个闭合图,因为点2是点1的后继,但不在闭合图中。《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》最大权闭合图《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》最大权闭合图构图增加源s汇t源s连接原图的正权点,容量为相应点权原图的负权点连接汇t,-670-3st《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》最大权闭合图解决复杂度为闭合图方案V’与不含正无限容量的割[S,T]一一对应闭合图V’的权为正权点总和减去对应割的容量割[S,T]取最小时,闭合图权取最大。《最小割模型在信息学竞赛中的应用》《最小割模型在信息学竞赛中的应用》