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

IOI2005国家集训队论文 王俊
浅析二分图匹配在信息学竞赛中的应用
湖南省长沙市长郡中学 王俊

[摘要]
本文通过对几道信息学竞赛题目的分析，举例说明了二分图匹配在信息学竞赛中的应用。二分图匹配的应用一般是通过分析某些最优化问题的性质，构造出二分图，再通过求得该二分图的最大匹配，最佳匹配等各种形式的匹配从而解决原问题。
[关键字]
匹配 二分图 最小权 最大权 优化
[正文]
一 引 言
二分图匹配是信息学竞赛中一类经典的图论算法，在近年来信息学竞赛中有广泛应用。如果可以以某一种方式将题目中的对象分成两个互补的集合，而需要求得它们之间满足某种条件的一一对应的关系时，往往可以抽象出对象以及对象之间的关系构造二分图，然后利用匹配算法来解决。这类题目通常需要考察选手对原题进行建模，构造二分图，设计匹配算法，并对其算法进行适当优化等多方面能力。下面就通过两道例题来说明二分图匹配在信息学竞赛中的一些应用。

二 Railway Communication Saratov State University 252. Railway Communication

2.1 问题描述
某国有n个城镇，m条单向铁路。每条铁路都连接着两个不同的城镇，且该铁路系统中不存在环。现需要确定一些列车运行线，使其满足：
I) 每条铁路最多属于一条列车运行线；
II) 每个城镇最多被一条列车运行线通过（通过包括作为起点或终点）；
III) 每个城镇至少被一条列车运行线通过；
IV) 列车运行线的数量应尽量小。
V) 在满足以上条件下列车运行线的长度和应该尽量小。
5
4
3
6
1
2
3
3
9
10三
13
1
图1

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')。
1
21
5
3
6
4
3'
2'
6'
1'
5'
4'
图2
X
Y

对于图G0中的任意一个结点i，可分为三类：
I) 某条覆盖路径的起点，即它没有前驱结点，那么在二分图G中点i' 的邻边均没有选。
II) 某条覆盖路径内部的点，即它有一个前驱结点和一个后继结点，那么在二分图G中i，i' 的邻边各选了1条。
III) 某条覆盖路径的终点，即它没有后继结点，那么在二分图G中点i的邻边均没有选。 如果某条覆盖路径只有一个结点的话，它显然满足性质I和性质III。

这样问题就转化成在二分图G中选一些边，且每个点的邻边中至多有一条被选中，显然这是一个二分图匹配的问题。又因为题目要求路径数最少，即路径终点数最少，即尽量多的匹配，所以是求该二分图的最大匹配，可以套用经典的匈牙利算法求解。
再来考虑求列车运行线总长度最小的问题。设原图G0中边(i，j)的边权为，则给图G的边(i，j')加入边权Wi，j ， (如图3)。原问题是求图G0中在保证覆盖路径数最少时求覆盖路径总长度最小，即在二分图G中求保证匹配数最大时匹配边的权值和最小。显然就是求图G的最小权最大匹配， 由于经典的KM算法是求最大权最大匹配，那么我们再对图G进行一定修改，使得，且如果，则添加边(i，j)，。其中w可以取一个比较大的正整数，但需要满足。这样用经典的KM算法求出二分图G的最大权最大匹配，即可轻易转化得到最小权最大匹配，从而解决原问题。
1
21
5
3
6
4
3'
2'
6'
1'
5'
4'
2
3
10
13
9
1
3
注：为了使图更简单清晰，省略了边权为无穷大的边。
图3
X
Y

2.3 小结
这道题目的数学模型很容易建立，就是最小路径覆盖问题的扩展。在分析该问题的时候抓住每个点在一条覆盖路径中至多有一个前驱一个后继这个条件，可以联系到匹配中每个点也至多和一个点匹配，于是顺利转化成匹配的问题。
一一对应是匹配重要的性质。

三 Roads Saratov State University 206. Roads

3.1 问题描述
一个遥远的王国有m条道路连接着n个城市。m条道路中有n-1条石头路, m-n+1条泥土路,任意两个城市之间有且仅有一条完全用石头路连接起来的道路。
每条道路都有一个唯一确定的编号，其中石头路编号为1..n-1，泥土路编号为n..m。每条道路都需要一定的维护费，其中第i条道路每年需要Ci的费用来维护。最近该国国王准备只维护部分道路以节省费用。但是他还是希望人们可以在任两个城市间互达。
国王需要你提交维护每条道路的费用，以便他能让他的大臣来挑选出需要维护的道路，使得维护这些道路的费用是最少的。
尽管国王不知道走石头路和走泥土路的区别，但是对于人民来说石头路似乎是更好的选择。为了人民的利益，你希望维护的道路是石头路。这样你不得不在提交给国王的报告中伪造维护费用。你需要给道路i伪造一个费用Di，使得这些石头路能够被挑选。为了不让国王发现，你需要使得真实值与伪造值的差值和尽量小。
国王的大臣当然不是白痴，全部由石头路组成的方案如果是一种花费最小的方案，那么他会选择这种方案。
求出真实值与伪造值的差值和的最小值，以及得到该最小值的方案，即每条边的修改后的边权Di。
红色边表示树T中的边
黑色边表示树T外的边
不带圈的数字表示边权
带圈的数字表示边编号
1
3
2
5
4
6
5
7
4
2
3
2
②
③
④
⑤
⑦
⑥
①
图4

3.2 问题分析
设原图为G0=(N0，A0)。其中N0表示顶点集合，A0表示边集合，即N0={1，2，……，n}，A0={a1，a2，……，am}。用Ci和Di表示原始及修改后边ai的边权。
由于任意两点都有且仅有一条道路完全是石头路，所以n-1条石头路必定是图G0中的一棵生成树，我们设为树T。而题目则是要求对图中的某些边权进行修改，对于边ai，将边权由Ci修改成Di，使得树T成为图中的一棵最小生成树，且最小。
实线表示树边
虚线表示非树边
1
3
2
5
4
t1
t2
t3
u
图5

根据与树T的关系，我们可以把图G0中的边分为树边和非树边两类。我们先通过对最小生成树性质的研究来挖掘D所需满足的条件。设P[e]表示边e的两个端点之间树的路径中边的集合。如图5中，, 即，而，且u与t1, t2, t3构成一个环，所以用非树边u替换树边t1，t2，t3中任意一条都可以得到一棵新的生成树。而如果u的边权比所替换的边的边权更小的话，则可以得到一棵权值更小的生成树。那么只有满足条件才能使得原生成树T是一棵最小生成树。
那么推广到一般情况，如果对于边v，u，其中，则必须满足，否则用边u替换边v后能得到一棵新的权值更小的生成树。
我们得到了D的限制条件，而问题需要求得最小，其中绝对值符号的存在是一个拦路虎。根据以上的分析，要使树T是一棵最小生成树，得到的不等式中v总为树边而u总为非树边。也就是树边的边权应该尽量小，而非树边的边权则应该尽量大。
设边权的修改量为，即
I) 当，则应该将边权Ce减去一个非负的值，即
II) 当，则应该将边权Ce加上一个非负的值，即
这样成功去掉了绝对值符号，只要求得的值，那么D值就可以唯一确定，而问题也由求D转化成求。
那么任意满足条件v，u()的不等式等价于，即。那问题就是求出所有的使其满足这个不等式组且最小。
由于不等式右边是一个已知量，你或许会发现这个不等式似曾相识，这就是我们在求二分图的最佳匹配算法时用到的KM算法中不可或缺的一个不等式。KM算法中，首先给二分图的每个点都设一个可行顶标，X结点i为li，Y结点j为ri。从初始时可行顶标的设定到中间可行顶标的修改直至最后算法结束，对于边权为的边(v，u)始终需要满足。
于是我们可以构造一个带权的二分图G=(N，A)，用W表示边权，如图6。
a) 构造两个互补的结点结合X，Y。把ai()作为X1结点i，aj()作为Y1结点j。
b) 如果图G0中，且，则在X1结点i与Y1结点j之间添加边(i，j)， 。
c) 如果，则添加个X2结点，；如果，则添加个Y2结点，。。
d) 如果，则添加边(i，j)，且
1
3
4
7
6
5
8
2
2
3
2
3
1
5
注：为了使图更简单清晰，省略了边权为0的边。
图6
X
Y

这样图G是一个二分完全图，设Q为图G的一个完备匹配，X结点i的可行顶标为li，Y结点j的可行顶标为rj，则：

设M为图G的最大权匹配，显然M也是完备匹配，则满足

设完备匹配Q的匹配边的权值和为SQ，显然
。
显然此时可行顶标之和取到最小值。
若，且，
由和
可知 ，所以
又因为，
所以， 同理
所以
显然SM即是满足T是图G0的一棵最小生成树的最小代价，而此时的D值则是修改后的一种可行方案，那么问题就转化为求图G的最大权完备M。
至此，问题已得到解决，我们来分析一下该算法的复杂度。预处理的时间复杂度为，而KM算法的时间复杂度为，所以总的时间复杂度为。由于KM算法是在完备匹配基础上的，所以，，又由于图G是二分完全图，所以，所以总的时间复杂度为。空间复杂度为。

3.3 扩展思考
如果题目只要求出最少的修改量，而不需要求出修改方案，那么是否有更好的算法呢？

3.3.1 算法1
现在需要求得的是原问题的一个子问题，利用KM算法来求出二分图G的最大权最大匹配，而即为所求，显然可以很好的解决该问题，其时间复杂度为。

3.3.2 算法2
可以发现，在构造二分图G时，其中c)，d)两个步骤中构造的都是一些虚结点和虚边，完全是为了符合KM算法要求完备匹配的条件，没有太多实际的意义。而利用KM算法解此题最大的优势就在于能求出修改方案，而如果题目不要求修改方案，则毫无意义，因此可试探不添加这些虚结点和虚边。
因为，且，所以，即最小修改量就是最大权最大匹配的匹配边的权值和，所以问题只需求出最大权最大匹配的值。
构造有向图Gf=(Nf，Af)，Wf表示边权，Uf表示容量，Rf表示流量，如图7。
a) 构造两个互补的结点集合Xf，Yf。把ai()作为Xf结点i，aj()作为Yf结点j。
b) 如果图G0中，且。则在Xf结点i与Yf结点j之间加入有向边(i，j)， 。
c) 构造源点s和汇点t，
d) 添加有向边(s，i) ，；添加有向边(j，t) ，。
1
3
4
7
6
5
s
2
2，1
3，1
2，1
3，1
1，1
5，1
t
0，1
0，1
0，1
0，1
0，1
0，1
0，1
红色数字表示边的费用
绿色数字表示边的容量
图7
Xf
Yf

[引理一] 设流F的费用和为CostF。图G上的任意一个完备匹配M，都能在图Gf上找到可行流F与其对应，且。而对于图Gf上的任意可行流F，在图G上的也都能找到一组以M为代表的完备匹配与其对应，且。
[证明] 对于图G中任意一条匹配边且，都可以找到图Gf中一条容量为1的流，其中。因为，所以；而当图G中且，则对SM的值不构成影响。所以当流F为匹配M所对应的流的并时，。而反过来对于任意可行流F，同样可以找到完备匹配M与其对应且。
设图Gf的最大费用最大流为F，显然图Gf的最大费用最大流则和图G的最大权最大匹配对应，此时最大费用就等于匹配的权值和，即。这样问题就转化为求图Gf的最大费用最大流。
如果用bellman_ford求最大费用路的算法来求最大费用最大流，则复杂度为,其中s表示流量。，所以复杂度为。

3.3.3 算法3
由于，所以算法二的时间复杂度和算法一的是一个级别的。观察可发现，用bellman_ford求最大费用路的复杂度为，成为算法2的瓶颈，如何减少求最大费用路的代价成为优化算法的关键，但由于残量网络中有负权边，导致类似Dijkstra等算法没有用武之地。这里介绍一种高效求单源最短路的SPFA（Shortest Path Faster Algorithm）算法。
设L记录从源点到其余各点当前的最短路径值。SPFA算法采用邻接表存储图，方法是动态优先逼近法。算法中设立一个先进先出的队列用来保存待优化的顶点，优化时每次取出队首结点p，并且用p点的当前路径值Lp去优化调整其他顶点的最优路径值Lj，若有调整，即Lj变小了，且j点不在当前的队列中，就将j点放入队尾以待进一步优化。就这样反复从队列取出点来优化其他点路径值，直至队列空不需要再优化为止。
由于每次优化都是将某个点j的最优路径值Lj变小，所以算法的执行会使L越来越小，所以其优化过程是正确的。只要图中不存在负环，则每个顶点都必定有一个最优路径值，所以随着L值逐渐变小，直到其达到最优路径值时，算法结束，所以算法是收敛的，不会形成无限循环。这样，我们简要地证明了该算法的正确性。
算法中每次取出队首结点p，并访问点p的所有邻结点的复杂度为，其中d为点p的出度。对于n个点e条边的图，结点的平均出度为，所以每处理一个点的复杂度为。设顶点入队的次数为h，显然h随图的不同而不同，但它仅与边的权值分布有关，设，则算法SPFA的时间复杂度为：。经过实际运行效果得到，k在一般情况下是比较小的常数（当然也有特殊情况使得k值较大），所以SPFA算法在普通情况下的时间复杂度为。
而此题中需要求的最大费用路显然可将SPFA算法稍加修改得到。这样我们得到了一个时间复杂度为，即的算法。

3.3.4 算法4
刚才用网络流来求匹配以提高效率，但未对匹配的本质进行深究，现在再回到匹配上来，继续挖掘匹配的性质。前面用KM算法解此题的时候是构造了一个边上带权的二分图，其实不妨换一种思路，将权值由边上转移到点上，或许会有新的发现。
构造二分图G '=(N '，A ')，如图8。
a) 构造两个互补的结点集合X '和Y '，把ai()作为X '结点i，aj()作为Y’结点j。
b) 在X '结点i和Y '结点i之间添加边(i，i)。
c) 如果图G0中，且。则在X '结点i与Y '结点j之间加入有向边(i，j)。
d) 给Y '结点i一个权值Ci，即如果某点被匹配则得到其权值。
1
3
4
3
2
1
2
4
6
5
7
6
2
5
7
3
2
4
图8
X'
Y'

[引理二] 设。对于图G中一个完备匹配M，都可以在图G '中找到一个完备匹配M '与其对应，且。而对于图G '的任意一个完备匹配M '，也可以在图G中找到一组以M为代表的完备匹配与其对应，且。
[证明] 设表示存在i使得的点j的集合；设表示存在i使得的点j的集合。
对于图G中一条匹配边(i，j) ，则Wi,j=0，对SM的值没有影响。
对于图G中一条匹配边(i，j) ，
若Wi,j=0，则在对应图G'中可找到一条边与其对应；
若Wi,j>0，则在对应图G'中可找到一条边与其对应。
所以

同理，图G '上的匹配M '也可以在图G上找到对应的匹配M且。
因为为定值。显然，当SM取到最大值时，SM'取到最小值。又因为M和M'均为完备匹配，所以图G的最大权最大匹配就对应了图G'的最小权完备匹配。那么问题转化为求图G'的最小权完备匹配。
由于图G' 中的权值都集中在Y' 结点上，所以SM'只与Y' 结点中哪些点被匹配有关。那么可以使Y ' 结点中权值小的结点尽量被匹配。算法也渐渐明了，将Y ' 结点按照权值大小非降序排列，然后从前往后一个个找匹配。
用R来记录可匹配点，如果X'结点，则i未匹配，或者从某个未匹配的X'结点有一条可增广路径到达点i，其路径用Path[i]来表示。设Bj表示j的邻结点集合，每次查询Y'结点j能否找到匹配时，只需看是否存在点i，。而每次找到匹配后马上更新R和Path。下面给出算法的流程：
Begin
将Y'结点按照权值非降序排列；
；
计算R及Path,并标记点i为可匹配点；
For to m do
Begin
第j个Y'结点；
If 存在q的某个邻结点p为可匹配点then
Begin
将匹配边(p，q)加入匹配M'；
更新R以及Path，并且重新标记点i为可匹配点；
End；
End；
M' 是一个最小权最大匹配；
End；

下面来分析一下该算法的复杂度。算法中执行了如下操作：
1） 将所有Y'结点按权值非降序排列；
2） 询问是否存在q的某个邻结点p为可匹配点；
3） 更新M'；
4） 更新R以及Path；
5） 标记点i为可匹配点；
操作1的时间复杂度为。设，操作2单次执行的复杂度为，最多执行m次，所以复杂度为。操作3单次执行的复杂度为，最多执行n-1次，所以复杂度为。操作5单次执行的复杂度为，最多执行n-1次，所以复杂度为。
接下来讨论操作4的复杂度。我们知道，如果某个点在某次更新中是不可匹配点，那么以后无论怎么更新它都不可能变成可匹配点。又如果某个点为可匹配点，则它的路径必然为，其中i0为未匹配点而且是当前的匹配边，所以Y'结点中未匹配点是不可能出现在某个X'点i的Path[i]中的。也就是说我们在更新R和Path的时候只需要在X'结点中原来的可匹配点以及Y'结点中已匹配点和它们之间的边构成的一个子二分图中进行，显然任意时刻图G'的匹配边数都是不超过n-1的，所以该子图的点数是的，边数是，显然单次执行操作4的复杂度即为，最多执行n次，所以其复杂度为。
算法总的时间复杂度为 ，因为dmax是级别的，所以该算法的时间复杂度为，其空间复杂度为。
其实本题还有更优秀的算法，但其推导与证明相对比较复杂，这里就不详细介绍了，大家可以参考相关论文。

3.4 小结
该题是一道最优化的问题，尝试发现动态规划，贪心等算法都无从下手。但经过一步步的分析，思路渐渐清晰，在得到了若干重要不等式后，问题豁然开朗，是一道求最佳匹配的问题，可以用经典的KM算法求解。
而在对不求方案的问题的研究中，不局限于直观的原图，而是从各个方向各个角度入手，构造不同的图，以展现题目各个方面的性质。也将算法复杂度由，优化到，再到，使效率大大提高。
下表是对上文研究的几个算法的简单比较：

时间复杂度
空间复杂度
算法核心
算法一

KM算法求最大权最大匹配
算法二

用bellman_ford算法求网络最大费用最大流增广路
算法三

用SPFA算法求网络最大费用最大流增广路
算法四

求结点带权的二分图的最小权匹配

四 总结
通过对以上的例题的分析可见，在信息学竞赛中，二分图匹配算法的应用往往不是显而易见的，而是需要挖掘出问题的本质，从而构造合适的二分图并用匹配算法来求解。而在求匹配的时候往往也不是简单的套用经典算法，而是需要充分利用题目的特有性质，将经典匹配算法加以变形，从而得到更高效的算法。
信息学竞赛中的各种题目，往往都需要通过对题目的仔细观察，构造出合适的数学模型，然后通过对题目以及模型的进一步分析，挖掘出问题的本质，进行大胆的猜想，转化模型，设计合适的算法解决问题。

[感谢]
衷心感谢向期中老师在学习上对我的指导和帮助
衷心感谢任恺、胡伟栋和周源同学对我的大力帮助
衷心感谢肖湘宁和周戈林两位同学对我的论文提出宝贵的意见

[参考文献]
[1] Ravindra K. Ahuja & James B. Orlin ，A Faster Algorithm for the Inverse Spanning Tree Problem
[2] 段凡丁，关于最短路径的SPFA快速算法

[附录]
例一原题：
Saratov State University 252. Railway Communication
time limit per test: 1 sec.
memory limit per test: 65536 KB
input: standard
output: standard

There are N towns in the country, connected with M railroads. All railroads are one-way, the railroad system is organized in such a way that there are no cycles. It's necessary to choose the best trains schedule, taking into account some facts.
Train path is the sequence of towns passed by the train. The following conditions must be satisfied.
1) At most one train path can pass along each railroad.
2) At most one train path can pass through each town, because no town can cope with a large amount of transport.
3) At least one train path must pass through each town, or town economics falls into stagnation.
4) The number of paths must be minimal possible.
Moreover, every railroad requires some money for support, i-th railroad requires c[i] coins per year to keep it intact. That is why the president of the country decided to choose such schedule that the sum of costs of maintaining the railroads used in it is minimal possible. Of course, you are to find such schedule.

Input
The first line of input contains two integers N and M (1<=N<=100; 0<=M<=1000). Next M lines describe railroads. Each line contains three integer numbers a[i], b[i] and c[i] - the towns that the railroad connects (1<=a[i]<=N; 1<=b[i]<=N, a[i]<>b[i]) and the cost of maintaining it (0<=c[i]<=1000). Since the road is one-way, the trains are only allowed to move along it from town a[i] to town b[i]. Any two towns are connected by at most one railroad.

Output
On the first line output K - the number of paths in the best schedule and C - the sum of costs of maintaining the railroads in the best schedule.
After that output K lines, for each train path first output L[i] (1<=L[i]<=N) - the number of towns this train path uses, and then L[i] integers identifying the towns on the train path. If there are several optimal solutions output any of them.

Sample test(s)

Input
4 4
1 2 1
1 3 2
3 4 2
2 4 2

Output
2 3
2 1 2
2 3 4

例二原题：
Saratov State University 206. Roads
time limit per test: 2 sec.
memory limit per test: 65536 KB
input: standard
output: standard

The kingdom of Farland has N cities connected by M roads. Some roads are paved with stones, others are just country roads. Since paving the road is quite expensive, the roads to be paved were chosen in such a way that for any two cities there is exactly one way to get from one city to another passing only the stoned roads.

The kingdom has a very strong bureaucracy so each road has its own ordinal number ranging from 1 to M: the stoned roads have numbers from 1 to N-1 and other roads have numbers from N to M. Each road requires some money for support, i-th road requires ci coins per year to keep it intact. Recently the king has decided to save some money and keep financing only some roads. Since he wants his people to be able to get from any city to any other, he decided to keep supporting some roads in such a way, that there is still a path between any two cities.

It might seem to you that keeping the stoned roads would be the good idea, however the king did not think so. Since he did not like to travel, he did not know the difference between traveling by a stoned road and travelling by a muddy road. Thus he ordered you to bring him the costs of maintaining the roads so that he could order his wizard to choose the roads to keep in such a way that the total cost of maintaining them would be minimal.

Being the minister of communications of Farland, you want to help your people to keep the stoned roads. To do this you want to fake the costs of maintaining the roads in your report to the king. That is, you want to provide for each road the fake cost of its maintaining di in such a way, that stoned roads form the set of roads the king would keep. However, to lower the chance of being caught, you want the value of sum(i = 1..M, |ci-di|) to be as small as possible.

You know that the king's wizard is not a complete fool, so if there is the way to choose the minimal set of roads to be the set of the stoned roads, he would do it, so ties are allowed.

Input
The first line of the input file contains N and M (2 ≤ N ≤ 60, N-1 ≤ M ≤ 400). Next M lines contain three integer numbers ai, bi and ci each — the numbers of the cities the road connects (1 ≤ ai ≤ N, 1 ≤ bi ≤ N, ai ≠ bi) and the cost of maintaining it (1 ≤ ci ≤ 10 000).

Output
Output M lines — for each road output di that should be reported to be its maintainance cost so that he king would choose first N-1 roads to be the roads to keep and the specified sum is minimal possible.

Sample test(s)

Input
4 5
4 1 7
2 1 5
3 4 4
4 2 5
1 3 1

Output
4
5
4
5
4

第 19 页 共 19 页