文档介绍：两极相通
——浅析最大最小定理在信息学竞赛中的应用
引入
我们在信息学竞赛中经常会遇到一些涉及一个最大化问题和一个最小化问题的定理
怎样利用这些定理帮助我们解题呢?
König定理
最大流—最小割定理
König定理
主要内容
在任何一个二部图G中,最大匹配数r(G)等于最小覆盖数c(G)
König定理
证明
最大匹配数不超过最小覆盖数
任取一个最小覆盖Q,一定可以构造出一个与之大小相等的匹配M
r(G) ≤ c(G)
r(G) = c(G)
c(G) ≤|Q| = |M| ≤ r (G) c(G) ≤ r(G)
König定理
应用
二部图最小覆盖和最大匹配的互相转化
[例一] Muddy Fields
最大流—最小割定理
近年来,网络流尤其是最大流问题越来越多的出现在各类信息学竞赛当中
最大流—最小割定理是整个最大流问题的基础与核心,其主要内容是:
最大流的流量不超过最小割的容量
存在一个流x和一个割c,且x的流量等于c的容量
[例二] Moving the Hay
一个牧场由R*C个格子组成
牧场内有N条干草运输通道,每条连接两个水平或垂直相邻的方格,最大运输量为Li
(1,1)内有很多干草,Farmer John希望将最多的干草运送到(R,C)内
求最大运输量
[例二] Moving the Hay
一个R=C=3的例子,最大运输量为7
数据规模:R,C ≤ 200
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(2,3)
(3,2)
(3,3)
5,5
3,2
5,5
2,2
1,1
6,6
4,1
7,6
(3,1)
分析
直接求最大流
以每个方格为点,每条通道为边,边的容量就是它的最大运输量
从(1,1)到(R,C)的最大运输量就是将这两个方格对应的点分别作为流网络中的源和汇求出的最大流量
效率???
点数最大40000,边数最大80000!
Time Limit Exceeded!!!
分析
效率低下的原因
没有利用题目的特点,直接套用经典算法
特点
题目中给出的是一个平面图
图中的一个点为源点s,另外一个点为汇点t,且s和t都在图中的无界面的边界上