IOI2005国家集训队论文王俊浅析二分图匹配在信息学竞赛中的应用湖南省长沙市长郡中学王俊[摘要]本文通过对几道信息学竞赛题目的分析，举例说明了二分图匹配在信息学竞赛中的应用。二分图匹配的应用一般是通过分析某些最优化问题的性质，构造出二分图，再通过求得该二分图的最大匹配，最佳匹配等各种形式的匹配从而解决原问题。[关键字]匹配二分图最小权最大权优化[正文]一引言二分图匹配是信息学竞赛中一类经典的图论算法，在近年来信息学竞赛中有广泛应用。如果可以以某一种方式将题目中的对象分成两个互补的集合，而需要求得它们之间满足某种条件的一一对应的关系时，往往可以抽象出对象以及对象之间的关系构造二分图，然后利用匹配算法来解决。这类题目通常需要考察选手对原题进行建模，构造二分图，设计匹配算法，并对其算法进行适当优化等多方面能力。下面就通过两道例题来说明二分图匹配在信息学竞赛中的一些应用。二RailwayCommunication12.1问题描述某国有n个城镇，m条单向铁路。每条铁路都连接着两个不同的城镇，且该铁路系统中不存在环。现需要确定一些列车运行线，使其满足：I)每条铁路最多属于一条列车运行线；II)每个城镇最多被一条列车运行线通过（通过包括作为起点或终点）；III)每个城镇至少被一条列车运行线通过；IV)列车运行线的数量应尽量小。V)在满足以上条件下列车运行线的长度和应该尽量小。1SaratovStateUniversity252.RailwayCommunication第1页共18页IOI2005国家集训队论文王俊2.2问题分析题目要求列车运行线数最少，又要求在此条件下列车运行线的长度和最小，不便于一起考虑，我们不妨分步研究，先考虑列车运行线数最少的子问题。则该子问题可建立如下数学模型：给定一个有向无环图G0=(N0，A0)，用尽量少的不相交的简单路径覆盖N0。我们可以给问题建立一个二分图G=(N，A)，如图2。a)建立两个互补的结点集合X和Y，把点i()拆成X结点i和Y结点i'。。b)对于图G0中有向边(i，j),,则在A中加入边(i，j')。如果在G0中选定(i，j)作为某条覆盖路径中的边，则在G中选定边(i，j')。第2页共18页54361233910三131图112153643'2'6'1'5'4'图2XYIOI2005国家集训队论文王俊对于图G0中的任意一个结点i，可分为三类：I)某条覆盖路径的起点，即它没有前驱结点，那么在二分图G中点i'的邻边均没有选。II)某条覆盖路径内部的点，即它有一个前驱结点和一个后继结点，那么在二分图G中i，i'的邻边各选了1条。III)某条覆盖路径的终点，即它没有后继结点，那么在二分图G中点i的邻边均没有选。2这样问题就转化成在二分图G中选一些边，且每个点的邻边中至多有一条被选中，显然这是一个二分图匹配的问题。又因为题目要求路径数最少，即路径终点数最少，即尽量多的匹配，所以是求该二分图的最大匹配，可以套用经典的匈牙利算法求解。再来考虑求列车运行线总长度最小的问题。设原图G0中边(i，j)的边权为，则给图G的边(i，j')加入边权Wi，j，(如图3)。原问题是求图G0中在保证覆盖路径数最少时求覆盖路径总长度最小，即在二分图G中求保证匹配数最大时匹配边的权值和最小。显然就是求图G的最小权最大匹配，由于经典的KM算法是求最大权最大匹配，那么我们再对图G进行一定修改，使得，且如果，则添加边(i，j)，。其中w可以取一个比较大的正整数，但需要满足。这样用经典的KM算法求出二分图G的最大权最大匹配，即可轻易转化得到最小权最大匹配，从而解决原问题。2如果某条覆盖路径只有一个结点的话，它显然满足性质I和性质III。第3页共18页12153643'2'6'1'5'4'231013913注：为了使图更简单清晰，省略了边权为无穷大的边。图3XYIOI2005国家集训队论文王俊2.3小结这道题目的数学模型很容易建立，就是最小路径覆盖问题的扩展。在分析该问题的时候抓住每个点在一条覆盖路径中至多有一个前驱一个后继这个条件，可以联系到匹配中每个点也至多和一个点匹配，于是顺利转化成匹配的问题。一一对应是匹配重要的性质。三Roads33.1问题描述一个遥远的王国有m条道路连接着n个城市。m条道路中有n-1条石头路,m-n+1条泥土路,任意两个城市之间有且仅有一条完全用石头路连接起来的道路。每条道路都有一个唯一确定的编...
