算法合集之《浅析最大最小定理在信息学竞赛中的应用》课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《算法合集之《浅析最大最小定理在信息学竞赛中的应用》课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浅析最大最小定理在信息学竞赛中的应用 算法 浅析 最大 最小 定理 信息学 竞赛 中的 应用 课件
- 资源描述:
-
1、浅析最大最小定理在信息学竞赛中的应用浅析最大最小定理在信息学竞赛中的应用 我们在信息学竞赛中经常会遇到一些涉及一个最大化问题和一个最小化问题的定理 怎样利用这些定理帮助我们解题呢?Knig定理定理最大流最大流最小割定理最小割定理 主要内容n在任何一个二部图G中,最大匹配数r(G)等于最小覆盖数c(G)证明n最大匹配数不超过最小覆盖数n任取一个最小覆盖Q,一定可以构造出一个与之大小相等的匹配Mr(G)c(G)r(G)=c(G)c(G)|Q|=|M|r (G)c(G)r(G)应用n二部图最小覆盖和最大匹配的互相转化n例一 Muddy Fields近年来,网络流尤其是最大流问题越来越多的出现在各类信
2、息学竞赛当中最大流最小割定理是整个最大流问题的基础与核心,其主要内容是:1.最大流的流量不超过最小割的容量2.存在一个流x和一个割c,且x的流量等于c的容量 一个牧场由R*C个格子组成 牧场内有N条干草运输通道,每条连接两个水平或垂直相邻的方格,最大运输量为Li(1,1)内有很多干草,Farmer John希望将最多的干草运送到(R,C)内 求最大运输量 一个R=C=3的例子,最大运输量为7 数据规模:R,C 200(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,2)(3,3)5,53,25,52,21,16,64,17,6(3,1)直接求最大流n以每个方格为点,每条通道为边
3、,边的容量就是它的最大运输量 n从(1,1)到(R,C)的最大运输量就是将这两个方格对应的点分别作为流网络中的源和汇求出的最大流量 效率?n点数最大40000,边数最大80000!Time Limit Exceeded!效率低下的原因n没有利用题目的特点,直接套用经典算法 特点n题目中给出的是一个平面图n图中的一个点为源点s,另外一个点为汇点t,且s和t都在图中的无界面的边界上452316f1f2f3f4 效率低下的原因n没有利用题目的特点,直接套用经典算法 特点n题目中给出的是一个平面图n图中的一个点为源点s,另外一个点为汇点t,且s和t都在图中的无界面的边界上n我们称这样的平面图为s-t平
4、面图平面图平面图性质1.(欧拉公式)如果一个连通的平面图有n个点,m条边和f个面,那么f=m-n+22.每个平面图G都有一个与其对偶的平面图G*n G*中的每个点对应G中的一个面4523161*2*3*4*平面图性质1.(欧拉公式)如果一个连通的平面图有n个点,m条边和f个面,那么f=m-n+22.每个平面图G都有一个与其对偶的平面图G*n G*中的每个点对应G中的一个面n 对于G中的每条边en e属于两个面f1、f2,加入边(f1*,f2*)4523161*2*3*4*平面图性质1.(欧拉公式)如果一个连通的平面图有n个点,m条边和f个面,那么f=m-n+22.每个平面图G都有一个与其对偶的
5、平面图G*n G*中的每个点对应G中的一个面n 对于G中的每条边en e属于两个面f1、f2,加入边(f1*,f2*)n e只属于一个面f,加入回边(f*,f*)4523161*2*3*4*平面图G与其对偶图G*之间存在怎样的关系呢?nG的面数等于G*的点数,G*的点数等于G的面数,G与G*边数相同nG*中的环对应G中的割一一对应4523161*2*3*4*如何利用这些性质?n直接求解仍然困难n利用最大流最小割定理转化模型转化模型根据平面图与其对偶图的关系,想办法求出最小割 对于一个s-t平面图,我们对其进行如下改造:n连接s和t,得到一个附加面附加面 对于一个s-t平面图,我们对其进行如下改
6、造:n求该图的对偶图G*,令附加面对应的点为s*,无界面对应的点为t*对于一个s-t平面图,我们对其进行如下改造:n删去s*和t*之间的边123456781*3*2*4*5*7*6*8*sts*t*一条从s*到t*的路径,就对应了一个s-t割!更进一步,如果我们令每条边的长度等于它的容量,那么最小割的容量就等于最短路的长度!分析一下时间复杂度n新图中的点数和边数都是O(n)的n使用二叉堆优化的Dijkstra算法求最短路,时间复杂度为O(nlog2n)123456781*3*2*4*5*7*6*8*sts*t*我们可以利用最短路算法得到的距离标号构造一个最大流 定理2.1 n可以在O(nlog
展开阅读全文