1、最小割模型在信息学竞赛中的应用Applications of Minimum Cut Modelin Informatics胡伯涛 AmberADN.cn福州第一中学 Fuzhou No.1 Middle School最小割定义 网络的割 S,T 将点集 V划分为 S和 T两部分， (其中源 s属于 S且汇 t属于 T)，而从 S指向 T的边组成割 割容量 割 中所有边的容量和 最小割 容量最小的割1 23 4ts最小割解法 最大流最小割定理网络的最大流流值该网络的最小割容量 求解最小割的有力武器 记表示在点数为 n，边数为 m的网络中求最大流 两个部分1.最大权闭合图标准解答的一个更一般化的
2、扩展模型 2.改进算法 达到用最大流解决该问题的理论下界 引入NOI 2006 最大获利 最小割是最大流的对偶问题。不直观，模型隐蔽。 展示最小割模型应用的巧妙构图方法和独特思维方式 网络流首次进入 NOINOI 2006 最大获利 (Profit)问题描述简要描述 有 n个结点， m条无向边可供建设。 建立一个结点 u有一定的花费 pu。建立一条无向边有一定的非负收益 we。 建立一条无向边 (u, v)的 必要条件 是要先建立点 u，点 v。 求最大获利。NOI 2006 最大获利 (Profit)分析 目的：选出一个边集 E, 点集 V。且最大化： 限制条件：对于在 E中每条边 (u,
3、v)，它的端点 u， v一定要在 V中。提出解决事件依赖关系的有力图论工具：闭合图。必要条件边依赖 点最大权闭合图 定义 有向图的 闭合图 （closure）：闭合图内任意点的任意后继也一定还在闭合图中。 物理意义事物间依赖关系：一个事件要发生，它需要的所有 前提 也都一定要发生。 最大权闭合图 是点权之和最大的闭合图。其中 3, 4, 5是一个闭合图。 3的后继 4， 4的后继 5，都在闭合图中。1 23 455 -67 0-3而 1, 4, 5不是一个闭合图，因为点 2是点 1的后继，但不在闭合图中。最大权闭合图解决复杂度为解法略去最大权闭合图构图 增加源 s汇 t 源 s连接原图的正权点，容量为相应点权 原图的负权点连接汇 t，容量为相应点权的相反数 原图边的容量为正无限 . 1 23 455 -67 0-3st63最大权闭合图解决复杂度为闭合图方案 V与不含正无限容量的割 S, T一一对应闭合图 V的权为正权点总和减去对应割的容量割 S, T取最小时，闭合图权取最大。
