1、目录 增广路定理与Hall定理 二分图最大基数匹配 二分图最大权匹配 应用Hopcroft算法 可以证明：如果每次找到的最短最短增广路集是极大极大的，则只需要增广 次 关键：用O(m)时间找一个极大最短增广路集 步骤步骤1：用距离标号扩展匈牙利树，找到第一个未盖点时并不停止，把此时的距离标号设为上限。这样，找到的所有未盖点距离标号都相同 步骤步骤2：每次任取一个未盖点，用DFS找到它到起点的增广路(只沿着距离标号下降的方向),标记经过的点,找所有增广路的总时间为O(m)()On基于DFS的算法 从贪心匹配贪心匹配,而不是空匹配开始 每次从一个一个未盖点开始DFS找增广路,而不是一次性把所有未盖
2、点放入队列进行BFS 如果从一个未盖点u开始找不到增广路,则以后再也不用考虑u了.为什么?定理定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配的增广路定理的证明(1)定理定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配M的增广路 证明证明:假设增广后从u出发有增广路Q.若Q与P不相交,则Q就是M-增广路,矛盾.因此Q与与P相交相交.下面借助P和Q构造出从u出发关于M的增广路,从而得到矛盾定理的证明(2)Q与P相交.设P的两个M-非饱和点为u0和v0,而Q的两个
3、M-非饱和点是u,v.从u开始沿Q走,设第一个P中结点为w,则w把P分为两段,其中必有一段以M中边与w关联,得到从u出发增广路wv0u0vuPQ完全二分图的最大权完美匹配 完全二分图，每条边有一个非负整数权值 目标：求出权和最大的完美匹配 特点：完美匹配容易求，但权最大的不易 可行顶标：可行顶标：结点函数l，对任意弧(x,y)满足 相等子图：相等子图：G的生成子图，包含所有点，但只包含满足l(x)+l(y)=w(x,y)的所有弧(x,y)()()(,)l xl yw x y相等子图 定理：定理：如果相等子图有完美匹配，则该匹配是原图的最大权匹配 证明：证明：设M*是相等子图的完美匹配，则根据定
4、义 设M是原图的任意完美匹配，则 关键：关键：寻找好的可行顶标，使相等子图有完美匹配*()()()v XYe Mw Mw el v*()()()()e Mv XYw Mw el vw M算法思想 关键：关键：寻找好的可行顶标，使相等子图有完美匹配 思想：思想：随便构造一个可行顶标（例如Y结点顶标为0，X结点的顶标为它出发所有弧的最大权值，然后求相等子图的最大匹配 存在完美匹配，算法终止 否则修改顶标使得相等子图的边变多，有更大机会存在完美匹配 考虑相等子图不存在完美匹配时的情形考虑相等子图不存在完美匹配时的情形Kuhn-Munkres算法 如右图，相等子图的最大匹配基数为6，不是完美匹配 算法
5、在寻找增广路失败的同时得到了一棵匈牙利树 虽然此匈牙利树并没有包含未盖点（因此没有找到增广路），但仍然含有重要信息Kuhn-Munkres算法 设匈牙利树中的X结点集为S，Y结点集为T，则 S到T没有边（否则匈牙利树可以继续生长）S到T的边都是非匹配边（想一想，为什么）但若把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图SSTTKuhn-Munkres算法 把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图 为了保证S-T的匹配边不离开相等子图，把T中所有点的顶标同时增加aSSTT-a+amin()()(,)|,al xl yw x yxS
6、 yT为保证有新边进入，取为保证有新边进入，取如果S中每个顶标的实际减小值比这个值小则不会有新边进入；如果比这个值大则顶标将变得不可行Kuhn-Munkres算法 设边(x,y)进入相同子图 y是未盖点，则找到增广路 y和S中的点z匹配，则把z和y分别加入S和T中 每次修改顶标要么找到增广路，要么使匈牙利树增加两个结点 因此一共需要O(n2)次修改顶标操作 关键：快速修改顶标SSTT-a+a顶标的修改 方法方法1：枚举S和T中的每个元素，根据定义计算最小值，每次修改的时间为O(n2)，总O(n4)方法方法2：对于T中的每个元素y，定义松弛量 则a的计算公式变为min()()(,)|,al xl
7、 yw x yxS yT()min()()(,)x Sslack yl xl yw x ymin()y Taslack y顶标的快速修改 每次增广后用O(n2)时间计算所有点的初始slack，由于每次生长匈牙利树时所有S-T弧的增量相同，因此修改每个slack值只需要常数时间，计算所有slack值需要O(n)时间 每次增广后最多修改n次顶标，因此每次增广后修改顶标总时间降为O(n2)，总O(n3)结论：Kuhn-Munkres算法的总时间复杂度为O(n3)()min()()(,)x Sslack yl xl yw x y例题1.Beloved Sons(SGU210)国王有N个儿子，另外有N漂
8、亮的女孩，每个儿子喜欢其中的某些。国王对每个儿子有一个喜爱程度。要把王子和这些女孩配对（不一定完全配对），使得所有被配对的王子被喜爱程度值的平方和尽可能大。分析 可以用二分图的最佳匹配 因为这个图有特殊性，男孩子一边任一个点连出的所有边的权值都是相同的，所以只要将男孩子按照国王的喜欢程度从大到小排序，先对国王更喜欢的孩子扩展增广路径，就可以得到最优解。这是为什么呢？分析 由增广路的性质可以知道一条增广路的应用只可能在匹配的男孩子中加入一个人，而不可能删去任意一个人。所以国王喜欢程度较低的男孩子进入匹配不可能对喜欢程度较高的孩子是否在匹配中产生任何影响：这就是贪心算法成立的原因。例题2.Domi
9、noes(SGU190)给定一个NN的棋盘，其中有一些格子被移除。要求在剩下的棋盘中放置互不重叠的12的骨牌，将棋盘盖满。分析 将棋盘黑白染色，使得黑格周围都是白格，白格周围都是黑格。黑白格构成了二分图的两个顶点集合，相邻的格子之间有边。这样，二分图的完备匹配就是问题的解了。实际上不需要单独建立二分图，直接在图上操作即可。点和边都是O(N2)个,因此时间复杂度为O(N3)例题3.Speleology(POI9906)一个山上有一个很大的洞，其中有n个室，编号为1n，室与室之间有通道。编号越大的室在越下方。有一批洞穴学者要从编号为1的室走到编号为n的室中，途中他们只能从编号小的地方走到编号大的地
10、方。每条和1或n相连的通道只允许一个人通过。问：最多可以有多少名洞穴学者？分析 我们可以把n个室看作n个点，把通道看作是点到点之间的一条有向边。那么本题就是一个典型的网络流问题。其中，每条和1或n相连的边容量为1,其他边容量为无穷大。1为源点，n为汇点。这个网络的最大流即为问题的解 其实这个图是特殊的,考虑1出发直接可达集合S和直接可达n的集合T之间的最大匹配例题4.Unstable Systems(SGU218)求一个完备匹配，使得匹配边中权值最大的边权值最小。分析 算法一 二分选择flow，并且进行最大匹配 算法二 从权值最低的边开始，每次增加一条边。维护交错树森林，最多只可能增加一个交错
11、轨。因为找到N条交错轨即可，而维护交错树森林的平摊复杂度为O(1)，所以总时间复杂度依然为O(N3)例题5.Greedy Island(ZOJ1638)有n(=10,000)种卡片，每种卡片上有三种属性：攻击、防御、超能力 从n张卡片中选A张作为攻击卡片，B张作为防御卡片，C张作为超能力卡片(A+B+C=100)。要求攻击卡片的总攻击值、防御卡片的总防御值和超能力卡片的总超能力值之和尽量大分析 令A+B+C=m，则m=100 如果一张卡片被选为攻击卡片，则它的攻击值不可能排不到前m位（这样前m位肯定有没选的，换成它则提高攻击值）这样，只需要保留攻击、防御和超能力各前100名，一共最多3m张（有
12、重复的话比这个少）。分析 算法一：算法一：构造二分图，左边3个点，表示攻击、防御、超能力三个用途；右边3m个点，表示所有需要考虑的卡片，则时间复杂度为O(m3)。算法二：算法二：左边只有3个点，因此可以设di,a,b,c表示前i张选了a张攻击卡片，b张防御卡片，c张超能力卡片，则状态转移是O(1)的（考虑下一张卡片的四种决策），状态不超过m4/9个，仍然高效例题6.Divide and Conquer(SGU229)N*N的方格上有一些格子着黑色.把它们分成两部分,使得其中一部分逆时针旋转90度、180度或270度后再平移,可以和另一部分重合分析 枚举旋转角度和平移向量,枚举量O(n2)每个点
13、变换后有一个唯一的象.对于每个黑点p,如果它的象也是黑点,则连一条有向边 则问题有解当且仅当此图有完美匹配 如果得到的图有度数为0的点或者自环,显然没有匹配,否则图是链和环的集合,各个连通分量很容易求出各自的最大匹配 时间复杂度为:O(n4)例题7.整数因子团问题 给整数n,考虑集合1,2,n.每次可以选择集合中的一个元素k,删除它和它在集合中的所有因子,要求每次至少删除两个数(即k至少有一个小于k的约数在集合中)例如,n=6时 方案一:依次选5,6,剩余序列为4 方案二:依次选5,4,6,剩余序列为空 输入n(=120),求一种方案让选择的数之和尽量大.注意选择的数并不等同于删除的数分析 似
14、乎并没有很好的方法,搜索吧 下界下界:一个不错的解,先贪心,搜索过程中不断改进为当前得到的最优解 上界上界:对当前状态的估计,应被设计为状态的函数.因为频繁调用,计算量不应太大 关键关键:最优性剪枝当前分数当前分数+当前状态的上界当前状态的上界 q存在且p出发只有一条边.删除q会让p没有办法删除,还不如主动选择p,效果是一样的.如果有多个p,显然应选择最大的一个 时间复杂度:O(nlog2n)上界 集合中每个数一个点,a/b是素数,则连一条边a-b,则数a是数b的倍数当且仅当a到b有有向道路.这样构图的好处是边比较少 结论结论:如果a可选,则a出发一定有边.证明证明:如果a出发的边都不存在了，
15、则根据游戏规则它的所有后代都将被删除,与a可选矛盾.最好情况:每次只被动删除一个数匹配 每条边a-b的权是a,则“每次选一个数删一个数”的最大得分是图的最大权匹配 结论：结论：不考虑边的方向，这个图是二分图 证明：证明：考虑每个数u的惟一分解式 每条边(u,v)满足u/v=p是素数，因此v的分解式中指数之和减1，奇偶性改变奇偶性改变 分解式中指数和为奇/偶的结点为X/Y结点1212kaaakupp.p匹配只是上界 考虑以下匹配：a)222，b)339，c)1133，d)1326 不难得出：a)在d)之前，d)在b)之前，b)在c)之前，c)在a)之前。而这是不可能实现的 不过n比较小时匹配结果
16、就是标准答案 虽然如此,这个上界是相容的,可以用作IDA*算法的估价函数不明智的选择 a至少有4个约数(包括自己),其中至少有一个比a的层次小2i)先删b更好 ii)先删c更好iii)不会出现(设b/c=p1,b/d=p2,则a/p1和a/p2分别是c和d的倍数,故没删除.但它们应和b同层)bacdbaabcd其他优化 检查相邻操作是否可交换 猜想猜想:存在一个数只有两个约数没有被删除,并且这个数的所有倍数(除了它自己)已被删除,那么删除满足条件的最大数是最优的a2cabacab2abcb2cbcca2bac2bc2猜想的反例 a,b,c是不同素数,abc,a2bn/2 贪心贪心:方案方案 先删除,ab2,后面最大ac2+bc2 更优方案更优方案:先删除ac2,再bc2,再abc 但n=120时反例不会出现a2cabacab2abcb2cbcca2bac2bc2运行结果 如果不用猜想,则7074,8186,105120都很慢 用上猜想则所有数据0.5秒以内出解N1030506580100105110120答案答案4030180813282041316434343764459346 结束语结束语
