算法合集之《浅析二分图匹配在信息学竞赛中的应用》

浅析二分图匹配在信息学竞赛中的应用[摘要]本文通过对几道信息学竞赛题目的分析，举例说明了二分图匹配在信息学竞赛中的应用。

二分图匹配的应用一般是通过分析某些最优化问题的性质，构造出二分图，再通过求得该二分图的最大匹配，最佳匹配等各种形式的匹配从而解决原问题。

[关键字]匹配二分图最小权最大权优化[正文]一引言二分图匹配是信息学竞赛中一类经典的图论算法，在近年来信息学竞赛中有广泛应用。

如果可以以某一种方式将题目中的对象分成两个互补的集合，而需要求得它们之间满足某种条件的一一对应的关系时，往往可以抽象出对象以及对象之间的关系构造二分图，然后利用匹配算法来解决。

这类题目通常需要考察选手对原题进行建模，构造二分图，设计匹配算法，并对其算法进行适当优化等多方面能力。

下面就通过两道例题来说明二分图匹配在信息学竞赛中的一些应用。

二Railway Communication1** 问题描述某国有n个城镇，m条单向铁路。

每条铁路都连接着两个不同的城镇，且该铁路系统中不存在环。

现需要确定一些列车运行线，使其满足：I)每条铁路最多属于一条列车运行线；II)每个城镇最多被一条列车运行线通过（通过包括作为起点或终点）；III)每个城镇至少被一条列车运行线通过；IV)列车运行线的数量应尽量小。

V)在满足以上条件下列车运行线的长度和应该尽量小。

1Saratov State University 252. Railway Communication** 问题分析题目要求列车运行线数最少，又要求在此条件下列车运行线的长度和最小，不便于一起考虑，我们不妨分步研究，先考虑列车运行线数最少的子问题。

则该子问题可建立如下数学模型：给定一个有向无环图G 0=(N 0，A 0)，用尽量少的不相交的简单路径覆盖N 0。

我们可以给问题建立一个二分图G =(N ，A )，如图2。

a) 建立两个互补的结点集合X 和Y ，把点i (0i N ∈)拆成X 结点i 和Y 结点i'。

序言：回忆起最初学习图匹配算法的艰辛与困惑，苦中有乐，但很多时间都浪费在了资料的寻找与甄别上。

因此，在对自己做一次知识总结的同时，整理与记录下了这些文字，希望能够给大家带来一定的帮助。

目录：第一部分：二分图的最大匹配第二部分：五种方式，两类构图第三部分：二分图匹配算法总结第四部分：二分图的最优权值匹配第五部分：一般图的最大匹配第六部分：图匹配题目列表符号说明：N,V：点数E：边数u,v,i,j：节点的标号INF：正无穷大-INF：负无穷大名词说明：时间复杂度：算法的理论时间上界时间效率：实际中算法运行的平均时间效率引用说明：文中参考了一些来源于网络的资料，也有原文全段引用的部分。

在这些资料被n+1次转载后，我已无法获知所有原作者的信息。

在此，对所有前辈们表示真诚的歉意和诚挚的敬意。

特别感谢Amber大神犀利的代码。

作者：Snow_storm正文：第一部分：二分图匹配有这么两个奇怪的工厂：工厂X只生产杯具，工厂Y只生产洗具。

最近，两个工厂决定将产品实行打包策略：即一个杯具搭配上一个洗具。

但由于杯具和洗具的形状和功能各不相同，对于某个类别的杯具来说，只能搭配某些类型的洗具。

现在，两个工厂的厂长大人想知道最多能成功的搭配多少对杯具与洗具。

类似于上面例子中提到的搭配问题，在图论中的有规范的名称：匹配。

注意到，上面的例子中涉及到的物品只有两类（杯具与洗具），且问题只涉及杯具与洗具的匹配，我们把这种只涉及一种关系的匹配问题称为二分匹配问题。

现在，让我们理清一些概念。

二分图：若图G中的点可以分为X和Y两部分，且每部分内部无任何边相连，则称图G为二分图。

匹配：无公共点的边集合（可以想象一下结婚这个词汇）。

匹配数：边集中边的个数最大匹配：匹配数最大的匹配。

如图1-1，展示的就是一个二分图：粗体线表示该二分图的一种匹配方式，不难发现，此时的匹配已经是最大匹配。

图 1-1如何能得到一个二分图的最大匹配？运用简单的枚举：找出全部匹配，然后保留匹配数最多的。

二分图匹配及其应用一、二分图基本概念1.二分图：无向图G的顶点集V分成两部分x和y，G中每条边的两个端点一定是一个属于x而另一个属于y，因此二分图可简记为G=（x,y,E）2.怎样判别二分图二分图的邻接矩阵一般具有如下形式对于较简单的图，可以直观地判断是否为二分图。

对于较复杂的图，可根据下列定义判断。

定理：当且仅当无向图G的每一个回路的长度均为偶数时，G是一个二分图。

如果无回路，相当于任一回路的长度为0，而0视为偶数。

证明：分别从必要性和充分性求证。

必要性：若G是二分图，则G的任一回路的长度为偶数。

设G中任一长度为m的回路C=Vi0,Vi1,…,Vi m-1,Vi m。

因G是二分图，因此可将V分为两个互补顶点子集V1和V2，对C来讲，将下标为偶数的顶点属于V1，下标为奇数的顶点属于V2，即Vi0,Vi2,…,Vi m-2∈V1，Vi1,Vi3,…,Vi m-1∈V2。

因m-1为奇数，故m为偶数。

充分性：若G的任一回路的长度为偶数时，G必是二分图，分两种情况讨论。

（1）G是连通图。

将图的顶点集合V按下列定义分为两个子集V1={Vi|V i与某一指定顶点V0的距离为偶数}，V2=V-V1下面证明，对于任一边e=（V i，V j）∈E，若V i∈V1，则V j∈V2设G中任一条边e=(Vi,Vj)，如果e的两个端点V i和V j都在V1中，则得到一个回路C=V i,…,V0,…,V j,V i因Vi,Vj∈V1，按定义V i和V j到V0的距离都是偶数，再加上边e，故回路C的长度为奇数，与题设矛盾，说明V i,V j不可能都在V i中。

如果e的两个端点V i和V j都在V2中，则按定义V i和V j到V0的距离都是奇数，再加上边e，故回路C的长度亦为奇数，与题设矛盾，说明V i和V j也不可能都处于V2中。

因此只有唯一一种可能，即e的两个端点，一个在V1中，另一个在V2中，由于e为G中任一条边，根据二分图定义，G是二分图。

⼆分图匹配问题最⼤匹配以及相关结论多重匹配最⼤带权匹配带花树算法⼆分图匹配问题：做法：①匈⽛利算法，时间复杂度O(N*V)②Hopcroft-Karp，时间复杂度O(√N*V)相关结论：①最⼩顶点覆盖(könig定理)　⼆分图的最⼩顶点覆盖=最⼤匹配数②最⼩路径覆盖（不要求⼆分图）：在图中找⼀些路径，使之覆盖了图中的所有顶点，且任何⼀个顶点有且只有⼀条路径与之关　最⼩路径覆盖 = 顶点数 - 最⼤匹配配对于有向⽆环图，⾸先拆点，建成⼆分图再进⾏求解·最⼩不相交路径覆盖　建图⽅式:把⼀个的点V拆点成Vx和Vy，如果A连向B，那么就建⼀条Ax连向By的边。

　图中有多少条路径，可以以⼀种⽅法得到，就是计算出度为0的点的个数。

如果知道这个就很容易得出这个结论了　·最⼩相交路径覆盖　做法⾸先跑floyd，求出原图的传递闭包，然后⽤上述⽅法做即可③最⼩边覆盖最⼩边覆盖=图顶点-最⼤匹配⾸先⼀开始，假如⼀条边都不选的话，要覆盖所有的点就必须每个点都选⼀次，也就是n次，然后每选⼀条边就会减少1个，所以结论显⽽易见④最⼤独⽴集最⼤独⽴集=图顶点-最⼤匹配=最⼩边覆盖⼆分图的独⽴数等于顶点数减去最⼤匹配数，很显然的把最⼤匹配两端的点都从顶点集中去掉这个时候剩余的点是独⽴集，这是|V|-2*|M|，同时必然可以从每条匹配边的两端取⼀个点加⼊独⽴集并且保持其独⽴集性质。

⼆分图多重匹配( ⼀ ) 如果x部节点只对应⼀个y部节点,⽽y部节点可以对应多个x部节点,那么这种匹配可以⽤匈⽛利算法来解决解决的问题：⼀个y最多匹配cnt个x是否成⽴，要问⼀个y匹配⼈数最⼤的最⼩值可以⽤⼆分答案来做解决思路：根据匈⽛利算法的思想，这时的link[u]要变成link[u][i],表⽰与y[u]匹配好了的第i个点，⽤vlink[u]记录已经于u点匹配了的点的个数，对于x中的x[k],找到⼀个与他相连的y[i]后，同样判断匈⽛利算法中的两个条件是否成⽴，若满⾜第⼀个条件，直接将x[k]，y[i]匹配，否则，如果与y[i]所匹配的点已经达到了饱和，那么在所有与y[i]配合的点中选⼀个点，检查能否找到增⼴路，如果能，就让出位置让x[k]与y[i]匹配( ⼆ )如果x部节点可以匹配多个y部节点,y部节点可以同时匹配多个x部节点,那么应该⽤⽹络流来解决。

二分图的最优匹配（KM算法）KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。

基本原理该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。

设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。

在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。

KM算法的正确性基于以下定理：若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。

首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。

这个定理是显然的。

因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。

所以相等子图的完备匹配一定是二分图的最大权匹配。

初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。

如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。

我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。

这时我们获得了一棵交错树，它的叶子结点全部是X顶点。

现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。

也就是说，它原来属于相等子图，现在仍属于相等子图。

2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。

算法合集之《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》线性规划的简单应用和实现浙江省杭州二中李宇骞摘要线性规划在实际生活中应用非常广泛，已经创造了无数的财富。

但是它在竞赛中的应用很少。

然而，我相信它的潜力很大，所以在这里向大家简单地介绍了线性规划的一些应用，以及如何实现解线性规划，以抛砖引玉，希望线性规划能够在竞赛中如同网络流一样熠熠生辉。

本文主要分三部分，第一部分简单地介绍了线性规划，给出了其定义；第二部分给出了一些简单的应用，以及一个线性规划的经典应用——多物网络流；第三部分是用单纯形（Simplex）算法实现解线性规划。

由于对大多数竞赛选手而言，写一个线性规划的程序比构造一个模型更为恐怖（虽然难度可能不及），并且单纯形法不是多项式级别的，不实践很难知道它的速度到底怎么样，所以本文着重于第三部分，较详细地描述了一些实现的细节，以及简单的证明，并且对单纯形法的运行速度做了一些实验，还与专业的数学软件MATLAB和LINDO做了对比，从一定程度上说明了单纯形法的速度是卓越的。

同时，200行左右的程序可以让大家不必那么担心编程的复杂度，某些情况下，100行左右的程序就足够了。

关键字线性规划（Linear programming）单纯形法（Simplex）多物网络流（Multicommodity flow）引言“随著强有力的算法的发展与应用,线性规划能解决的问题也越来越来多。

在历史上，没有哪种数学方法可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史的进程发生如此直接的影响。

”孙捷，这位曾经执教于清华大学的美国华盛顿大学博士如此评价线性规划。

他还举了这样一个实例：在波斯湾战争期间，美国军方利用线性规划，有效地解决了部队给养和武器调运问题，对促进战争的胜利，起了关键的作用。

难怪人们说，因为使用炸药，第一次世界大战可说是「化学的战争」；因为使用原子弹，第二次世界大战可说是「物理的战争」；因为使用线性规划，波斯湾战争可称为「数学的战争」。

二分上界(或答案)法的应用前言：在当今的信息学竞赛中，很多题目都令人无从下手，但如果我们先假定出题目的答案，问题就立刻迎刃而解。

下面我们从几道例题谈谈二分答案法的应用。

例题一：草莓(noi2003)题意简述：定义：S"皿表示第/块草莓田中所有草莓重量的和(1< 1< k) Ox = min {sug |1 < j “}你的任务就是要把一片草莓田分割成k块,且分割方案需要满足如下的条件：1•每一块中的草莓必然是通过触须直接或者间接和其他草莓相连接的；2.这种分割方案所对应的x尽可能的大。

最后输出你的分割方案和结果。

算法分析：这是一道结果提交类问题，其中有6个数据都是树，现在我们对树的问题进行讨论。

初一看，这题很难找到有效的模型，关键在于有的时候切出sum很大的一块反而不好，因为题目中需要的是相对平均，因此，纯粹的贪心很难成立。

我们试着稍微改变一下题目，假设题目要求求一种答案不小于x的方法，我们该如何处理呢？很快我们有了头绪，首先通过宽度搜索建树，然后从叶子结点开始向上处理，如果有以某个结点为根的子树的权值和超过了x,我们就将该结点以及它所在的子树作为一个连通块，从图中删去。

这样的做法一定是正确的，因为sum—旦超过了x,如果把更多的结点给这个连通块显然是没有必要的。

一直进行这样的处理，如果割出了k个连通块以上，则问题有解，否则问题无解。

因为只要扫描一遍，因此这个问题的时间复杂度为O(N)o既然我们已经可以在0(N)的时间类解决上述子问题，那么能比较高效地求解原题呢？我们可以枚举每一个x再加以判断，这样复杂度较高。

比较好的方法是采用二分法，假如一个解在某个去间[a, b],首先我们判断(a+b)/2是否可行，如果可行，则枚举[(a+b)/2+l,b],否则枚举[a,(a+b)/2-l]o那么，只需判断logm 次即可(其中m为所有点的权值和)。

如果不知道x,可不可以用上面的方法呢？答案是否定的，因为你不知道剩下部分的情况，所以无法在恰当的时候做出正确的选择。