浅析二分图匹配在信息学竞赛中的应用
浅析二分图匹配在信息学竞赛中的应用
[摘要]
本文通过对几道信息学竞赛题目的分析，举例说明了二分图匹配在信息学竞赛中的应用。二分图匹配的应用一般是通过分析某些最优化问题的性质，构造出二分图，再通过求得该二分图的最大匹配，最佳匹配等各种形式的匹配从而解决原问题。
[关键字]
匹配二分图最小权最大权优化
[正文]
一引言
二分图匹配是信息学竞赛中一类经典的图论算法，在近年来信息学竞赛中有广泛应用。如果可以以某一种方式将题目中的对象分成两个互补的集合，而需要求得它们之间满足某种条件的一一对应的关系时，往往可以抽象出对象以及对象之间的关系构造二分图，然后利用匹配算法来解决。这类题目通常需要考察选手对原题进行建模，构造二分图，设计匹配算法，并对其算法进行适当优化等多方面能力。下面就通过两道例题来说明二分图匹配在信息学竞赛中的一些应用。
二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 X Y =?。
b) 对于图G 0中有向边(i ，j ), 0(,)i j A ∈, 则在A 中加入边(i ，j ')。如果在G 0
中选定(i ，j )作为某条覆盖路径中的边，则在G 中选定边(i ，j ')。
对于图G 0中的任意一个结点i ，可分为三类：
1
2
5
3
6
4
3' 2' 6'
1' 5' 4' 图2
X
Y
2
5 4
3
6
1 2
3
3
9
1013
1
图1
I) 某条覆盖路径的起点，即它没有前驱结点，那么在二分图G 中点i' 的邻
边均没有选。
II) 某条覆盖路径内部的点，即它有一个前驱结点和一个后继结点，那么在
二分图G 中i ，i' 的邻边各选了1条。
III) 某条覆盖路径的终点，即它没有后继结点，那么在二分图G 中点i 的邻
边均没有选。2
这样问题就转化成在二分图G 中选一些边，且每个点的邻边中至多有一条被选中，显然这是一个二分图匹配的问题。又因为题目要求路径数最少，即路径终点数最少，即尽量多的匹配，所以是求该二分图的最大匹配，可以套用经典的匈牙利算法求解。
再来考虑求列车运行线总长度最小的问题。设原图G 0中边(i ，j )的边权为
0,i j W ，则给图G 的边(i ，j')加入边权W i ，j ，0,,i j i j W W = (如图3)。原问题是求图G 0中在保证覆盖路径数最少时求覆盖路径总长度最小，即在二分图G 中求保证匹配数最大时匹配边的权值和最小。显然就是求图G 的最小权最大匹配， 由于经典的KM 算法是求最大权最大匹配，那么我们再对图G 进行一定修改，使得
()()0,,,i j i j
W w W i j A =-∈，且如果(),i j A ?，则添加边(i ，j )，,0i j
W
=。其中w
可以取一个比较大的正整数，但需要满足{}()00,max ,i j w W n
i j A >?∈。这样用
经典的KM 算法求出二分图G 的最大权最大匹配，即可轻易转化得到最小权最大匹配，从而解决原问题。
** 小结
2
如果某条覆盖路径只有一个结点的话，它显然满足性质I 和性质III 。
1
2
5
3
6
4
3' 2' 6'
1' 5' 4' 2
3 10
13 9 1 3 注：为了使图更简单清晰，省略了边权为无穷大的边。
图3
X
Y
这道题目的数学模型很容易建立，就是最小路径覆盖问题的扩展。在分析该问题的时候抓住每个点在一条覆盖路径中至多有一个前驱一个后继这个条件，可以联系到匹配中每个点也至多和一个点匹配，于是顺利转化成匹配的问题。
一一对应是匹配重要的性质。
三 Roads 3
** 问题描述
一个遥远的王国有m 条道路连接着n 个城市。m 条道路中有n -1条石头路, m -n +1条泥土路,任意两个城市之间有且仅有一条完全用石头路连接起来的道路。
每条道路都有一个唯一确定的编号，其中石头路编号为1..n -1，泥土路编号为n ..m 。每条道路都需要一定的维护费，其中第i 条道路每年需要C i 的费用来维护。最近该国国王准备只维护部分道路以节省费用。但是他还是希望人们可以在任两个城市间互达。
国王需要你提交维护每条道路的费用，以便他能让他的大臣来挑选出需要维护的道路，使得维护这些道路的费用是最少的。
尽管国王不知道走石头路和走泥土路的区别，但是对于人民来说石头路似乎是更好的选择。为了人民的利益，你希望维护的道路是石头路。这样你不得不在提交给国王的报告中伪造维护费用。你需要给道路i 伪造一个费用D i ，使得这些石头路能够被挑选。为了不让国王发现，你需要使得真实值与伪造值的差值和
1m
i i i f D C ==-∑尽量小。
国王的大臣当然不是白痴，全部由石头路组成的方案如果是一种花费最小的方案，那么他会选择这种方案。
求出真实值与伪造值的差值和的最小值，以及得到该最小值的方案，即每条边的修改后的边权D i 。
3
Saratov State University 206. Roads
** 问题分析
设原图为G 0=(N 0，A 0)。其中N 0表示顶点集合，A 0表示边集合，即N 0={1，2，……，n }，A 0={a 1，a 2，……，a m }。用C i 和D i 表示原始及修改后边a i 的边权。
由于任意两点都有且仅有一条道路完全是石头路，所以n -1条石头路必定是图G 0中的一棵生成树，我们设为树T 。而题目则是要求对图中的某些边权进行修改，对于边a i ，将边权由C i 修改成D i ，使得树T 成为图中的一棵最小生成树，且1m
i i i f D C ==-∑最小。
根据与树T 的关系，我们可以把图G 0中的边分为树边和非树边两类。我们先通过对最小生成树性质的研究来挖掘D 所需满足的条件。设P [e ]表示边e 的
实线表示树边 虚线表示非树边
1 3
2
5
4
t 1 t 2
t 3
u
图5
红色边表示树T 中的边 黑色边表示树T 外的边 不带圈的数字表示边权 带圈的数字表示边编号
1 3
2
5 4
6 5
7 4 2 3 2
② ③ ④
⑤
⑦
⑥
① 图4
两个端点之间树的路径中边的集合。如图5中，{}123[],,P u t t t =, 即u T ?，而
123,,t t t T ∈，且u 与t 1, t 2, t 3构成一个环，所以用非树边u 替换树边t 1，t 2，t 3中任意一条都可以得到一棵新的生成树。而如果u 的边权比所替换的边的边权更小的话，则可以得到一棵权值更小的生成树。那么只有满足条件
123,,t u t u t u D D D D D D ≤≤≤才能使得原生成树T 是一棵最小生成树。
那么推广到一般情况，如果对于边v ，u ，其中[],v P u u T ∈?，则必须满足
v u D D ≤，否则用边u 替换边v 后能得到一棵新的权值更小的生成树T v u -+。
我们得到了D 的限制条件，而问题需要求得1m
i i i D C =-∑最小，其中绝对值符
号的存在是一个拦路虎。根据以上的分析，要使树T 是一棵最小生成树，得到的不等式v u D D ≤中v 总为树边而u 总为非树边。也就是树边的边权应该尽量小，而非树边的边权则应该尽量大。
设边权的修改量为?，即e e e D C ?=-
I) 当e T ∈，则应该将边权C e 减去一个非负的值，即e e e C D ?=- II) 当e T ?，则应该将边权C e 加上一个非负的值，即e e e D C ?=-
这样成功去掉了绝对值符号，只要求得?的值，那么D 值就可以唯一确定，而问题也由求D 转化成求?。
那么任意满足条件v ，u ([],v P u u T ∈?)的不等式v u D D ≤等价于
v v u u C C -?≤+?，即v u v u C C ?+?≥-。那问题就是求出所有的([1,])i i m ?∈使其满足这个不等式组且1m
i i f ==?∑最小。
由于不等式v u v u C C ?+?≥-右边v u C C -是一个已知量，你或许会发现这个不等式似曾相识，这就是我们在求二分图的最佳匹配算法时用到的KM 算法中不可或缺的一个不等式。KM 算法中，首先给二分图的每个点都设一个可行顶标，X 结点i 为l i ，Y 结点j 为r i 。从初始时可行顶标的设定到中间可行顶标的修改直至最后算法结束，对于边权为,v u W 的边(v ，u )始终需要满足,v u v u l r W +≥。
于是我们可以构造一个带权的二分图G =(N ，A )，用W 表示边权，如图6。 a) 构造两个互补的结点结合X ，Y 。把a i (i a T ∈)作为X 1结点i ，a j (j a T ?)
作为Y 1结点j 。
b) 如果图G 0中[],i j j a P a a T ∈?，且0i j C C ->，则在X 1结点i 与Y 1结点j
之间添加边(i ，j )，,i j i j W C C =- 。
c) 如果11X Y <，则添加11Y X -个X 2结点，2Y =?；如果11Y X <，则添
加11X Y -个Y 2结点，2X =?。1212,,X X X Y Y Y N X Y =?=?=?。 d) 如果,(,)i X j Y i j A ∈∈?且，则添加边(i ，j )，且,0i j W =
这样图G 是一个二分完全图，设Q 为图G 的一个完备匹配，X 结点i 的可行顶标为l i ，Y 结点j 的可行顶标为r j ，则：
(),(,)i j i j
l r W i j Q +≥∈ 设M 为图G 的最大权匹配，显然M 也是完备匹配，则满足
(),(,)i j i j
l r W i j M +=∈
设完备匹配Q 的匹配边的权值和为S Q ，显然
,(,)M i j i j i j M
i X
j Y
S W l r ∈∈∈==+∑∑∑ 。
显然此时可行顶标之和取到最小值。 若2i X ∈，且(,)i j M ∈，
由,20((,),)v u W v u A v X =∈∈和M A ?
1
3
4
7
6
5
8
2
3
2
3
1
5 注：为了使图更简
单清晰，省略了边权为0的边。
图6
X
Y
可知 ,0i j W =，所以 ,0i j i j l r W +== 又因为0()i l i X ≥∈，2X X ?
所以20()i l i X =∈， 同理 20()j r j Y =∈ 所以1
1
1m
M i j i j i i X
j Y
i X j Y i S l r l r f ∈∈∈∈==+=+=?=∑∑∑∑∑
显然S M 即是满足T 是图G 0的一棵最小生成树的最小代价，而此时的D 值则是修改后的一种可行方案，那么问题就转化为求图G 的最大权完备M 。
至此，问题已得到解决，我们来分析一下该算法的复杂度。预处理的时间复杂度为()O E ，而KM 算法的时间复杂度为()O M E ，所以总的时间复杂度为
()O M E 。由于
KM 算法是在完备匹配基础上的，所以
{}2max 1,1V n m n =--+，()2V
M O m ==，又由于图G 是二分完全图，所以()2
2E M O m ==，所以总的时间复杂度为()3O m 。空间复杂度为()2O m 。
** 扩展思考
如果题目只要求出最少的修改量，而不需要求出修改方案，那么是否有更好的算法呢？
** 算法1
现在需要求得的是原问题的一个子问题，利用KM 算法来求出二分图G 的最大权最大匹配，而min f 即为所求，显然可以很好的解决该问题，其时间复杂度为()
3O m 。
** 算法2
可以发现，在构造二分图G 时，其中c )，d )两个步骤中构造的都是一些虚结点和虚边，完全是为了符合KM 算法要求完备匹配的条件，没有太多实际的意义。而利用KM 算法解此题最大的优势就在于能求出修改方案，而如果题目不要求修改方案，则毫无意义，因此可试探不添加这些虚结点和虚边。
因为1
m
i i j i i X
j Y
f l r =∈∈=?=+∑∑∑，且(),(,)i j i j
l r W i j M +=∈，
所以(),,i j i j M
f W ∈=
∑
，
即最小修改量就是最大权最大匹配的匹配边的权值和，所以问题只需求出最大权最大匹配的值。
构造有向图G f =(N f ，A f )，W f 表示边权，U f 表示容量，R f 表示流量，如图7。
a) 构造两个互补的结点集合X f ，Y f 。把a i (i a T ∈)作为X f 结点i ，a j (j a T ?)
作为Y f 结点j 。
b) 如果图G 0中[],i j j a P a a T ∈?，且0i j C C ->。则在X f 结点i 与Y f 结点j
之间加入有向边(i ，j )，,,,1f f i j i j i j W C C U =-= 。 c) 构造源点s 和汇点t ，{,}f f f N X Y s t =??
d) 添加有向边(s ，i ) ()f i X ∈，,,0,1f f s i s i W U ==；
添加有向边(j ，t ) ()f j Y ∈，,,0,1f f j t j t W U ==。
[引理一] 设流F 的费用和为Cost F 。图G 上的任意一个完备匹配M ，都能在图G f 上找到可行流F 与其对应，且M F S Cost =。而对于图G f 上的任意可行流F ，在图G 上的也都能找到一组以M 为代表的完备匹配与其对应，且F M Cost S =。 [证明] 对于图G 中任意一条匹配边(),i j M ∈且,0i j W >，都可以找到图G f 中一条容量为
1
的流s i j t →→→，其中,f f i X j Y ∈∈。因为
,,,,0,0,f f f s i j t i j i j W W W W ===，所以,,,,f f f i j s i i j j t W W W W =++；而当图G 中(),i j M ∈且,0i j W =，则对S M 的值不构成影响。所以当流F 为匹配M 所对应的流的并时，
(),,,(,)f M i j i j
F i j M
i j F
S W W
Cost ∈∈=
=
=∑
∑。而反过来对于任意可行流F ，同样可以找到完
备匹配M 与其对应且F M Cost S =。
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
X f
Y f
设图G f 的最大费用最大流为F ，显然图G f 的最大费用最大流则和图G 的最大权最大匹配对应，此时最大费用就等于匹配的权值和，即
,,,(,)(,)f f F i j i j i j i j F
i j M
Cost W R W ∈∈=?=∑∑。
这样问题就转化为求图G f 的最大费用最大流。 如果用bellman_ford 求最大费用路的算法来求最大费用最大流，则复杂度为
()O V E s ,其中s 表示流量。(),(),()V O m E O nm s O n ===，所以复杂度为
()22O n m 。
** 算法3
由于2
()m O n =，所以算法二的时间复杂度()22O n m 和算法一的()
3O m 是一个级别的。观察可发现，用bellman_ford 求最大费用路的复杂度为()
O V E ，成为算法2的瓶颈，如何减少求最大费用路的代价成为优化算法的关键，但由于残量网络中有负权边，导致类似Dijkstra 等算法没有用武之地。这里介绍一种高效求单源最短路的SPF A （Shortest Path Faster Algorithm ）算法。
设L 记录从源点到其余各点当前的最短路径值。SPF A 算法采用邻接表存储图，方法是动态优先逼近法。算法中设立一个先进先出的队列用来保存待优化的顶点，优化时每次取出队首结点p ，并且用p 点的当前路径值L p 去优化调整其他顶点的最优路径值L j ，若有调整，即L j 变小了，且j 点不在当前的队列中，就将j 点放入队尾以待进一步优化。就这样反复从队列取出点来优化其他点路径值，直至队列空不需要再优化为止。
由于每次优化都是将某个点j 的最优路径值L j 变小，所以算法的执行会使L 越来越小，所以其优化过程是正确的。只要图中不存在负环，则每个顶点都必定有一个最优路径值，所以随着L 值逐渐变小，直到其达到最优路径值时，算法结束，所以算法是收敛的，不会形成无限循环。这样，我们简要地证明了该算法的正确性。
算法中每次取出队首结点p ，并访问点p 的所有邻结点的复杂度为()O d ，
其中d 为点p 的出度。对于n 个点e 条边的图，结点的平均出度为e
n
，所以每处
理一个点的复杂度为e O n ??
???。设顶点入队的次数为h ，显然h 随图的不同而不同，
但它仅与边的权值分布有关，设h kn =，则算法SPF A 的时间复杂度为：
()e h T O h O e O ke n n ????
=?=?= ? ?????。经过实际运行效果得到，k 在一般情况下是比
较小的常数（当然也有特殊情况使得k 值较大），所以SPF A 算法在普通情况下的时间复杂度为()O e 。
而此题中需要求的最大费用路显然可将SPF A 算法稍加修改得到。这样我们
得到了一个时间复杂度为()O E s ，即()2O n m 的算法。
** 算法4
刚才用网络流来求匹配以提高效率，但未对匹配的本质进行深究，现在再回到匹配上来，继续挖掘匹配的性质。前面用KM 算法解此题的时候是构造了一个边上带权的二分图，其实不妨换一种思路，将权值由边上转移到点上，或许会有新的发现。
构造二分图G '=(N '，A ')，如图8。
a) 构造两个互补的结点集合X '和Y '，把a i (i a T ∈)作为X '结点i ，a j ('j a A ∈)作为Y ’结点j 。
b) 在X '结点i 和Y '结点i 之间添加边(i ，i )。
c) 如果图G 0中[],i j j a P a a T ∈?，且0i j C C ->。则在X '结点i 与Y '结点j 之间加入有向边(i ，j )。
d) 给Y '结点i 一个权值C i ，即如果某点被匹配则得到其权值。
[引理二] 设i i a T
C μ∈=∑。对于图G 中一个完备匹配M ，都可以在图G '中找到一个
完备匹配M '与其对应，且'M M S S μ=-。而对于图G '的任意一个完备匹配M '，
1
34 3 2 1 2 4 6 5 7 6
2
5
7
3
2
4
图8 X'
Y'
也可以在图G 中找到一组以M 为代表的完备匹配与其对应，且'M M S S μ=-。 [证明] 设1'Y 表示存在i ()i j ≠使得(),'i j M ∈的点j 的集合；设2'Y 表示存在i ()i j =使得(),'i j M ∈的点j 的集合。
对于图G 中一条匹配边(i ，j ) ()2,i j M i X ∈∈且，则W i,j =0，对S M 的值没有影响。 对于图G 中一条匹配边(i ，j ) ()1,i j M i X ∈∈且，
若W i,j =0，则在对应图G'中可找到一条边(),'i j M ∈()2','i X j Y i j ∈∈=且与其对应；
若W i,j >0，则在对应图G'中可找到一条边(),'i j M ∈()1','i X j Y ∈∈与其对应。 所以
,,2121,(,),(,),0
(,),0
'''''
i j i j i i M i j
i j M
i j i j M W i j
i j M W i j j
a T j Y j Y i j j a T j Y j Y M S W W C C C C C C C C S μ∈∈>∈>∈∈∈∈∈∈===
-??
=-- ?????
=-+ ???=-∑
∑∑
∑∑∑∑∑∑
同理，图G '上的匹配M '也可以在图G 上找到对应的匹配M 且'M M S S μ=-。
因为'M M S S μ+=为定值。显然，当S M 取到最大值时，S M '取到最小值。又因为M 和M '均为完备匹配，所以图G 的最大权最大匹配就对应了图G '的最小权完备匹配。那么问题转化为求图G'的最小权完备匹配。
由于图G ' 中的权值都集中在Y' 结点上，所以S M '只与Y' 结点中哪些点被匹配有关。那么可以使Y ' 结点中权值小的结点尽量被匹配。算法也渐渐明了，将Y ' 结点按照权值大小非降序排列，然后从前往后一个个找匹配。
用R 来记录可匹配点，如果X'结点i R ∈，则i 未匹配，或者从某个未匹配的X'结点有一条可增广路径到达点i ，其路径用Path [i ]来表示。设B j 表示j 的邻
结点集合，每次查询Y'结点j 能否找到匹配时，只需看是否存在点i ，
j i B i R ∈∈且。而每次找到匹配后马上更新R 和Path 。下面给出算法的流程：
Begin
将Y'结点按照权值非降序排列； '0M ←；
计算R 及Path ,并标记点i ()i R ∈为可匹配点； For 1j ← to m do Begin q ←第j 个Y'结点；
If 存在q 的某个邻结点p 为可匹配点then Begin 将匹配边(p ，q )加入匹配M'；
更新R 以及Path ，并且重新标记点i ()i R ∈为可匹配点；
End ；
End ；
M' 是一个最小权最大匹配； End ；
下面来分析一下该算法的复杂度。算法中执行了如下操作： 1）将所有Y'结点按权值非降序排列；
2）询问是否存在q 的某个邻结点p 为可匹配点； 3）更新M'；
4）更新R 以及Path ；
5）标记点i ()i R ∈为可匹配点； 操作
1
的时间复杂度为()222log (log )O m m O n n =。设
{}
[]max max 1,j
d B j m =∈，操作2单次执行的复杂度为()
j O B ，最多执行m 次，
所以复杂度为()()2max max O md O n d =。操作3单次执行的复杂度为()1O ，最多执行n -1次，所以复杂度为()O n 。操作5单次执行的复杂度为()O n ，最多执行n -1次，所以复杂度为()2O n 。
接下来讨论操作4的复杂度。我们知道，如果某个点在某次更新中是不可匹
配点，那么以后无论怎么更新它都不可能变成可匹配点。又如果某个点为可匹配点，则它的路径必然为01122(0)k k
i j i j i j i k →→→→→
→→≥，其中i 0为
未匹配点而且[]()(,)1,t t j i t k ∈是当前的匹配边，所以Y'结点中未匹配点是不可能出现在某个X'点i 的Path [i ]中的。也就是说我们在更新R 和Path 的时候只需要在X '结点中原来的可匹配点以及Y'结点中已匹配点和它们之间的边构成的一个子二分图中进行，显然任意时刻图G'的匹配边数都是不超过n -1的，所以该子图的点数是()O n 的，边数是()max O nd ，显然单次执行操作4的复杂度即为
()max O nd ，最多执行n 次，所以其复杂度为()2max O n d 。
算法总的时间复杂度为()()()()()22222max max log O n n O n d O n O n d O n ++++
()()2max 2log O n d n =+，因为d max 是()O n 级别的，所以该算法的时间复杂度为
()3O n ，其空间复杂度为()O nm 。
其实本题还有更优秀的算法，但其推导与证明相对比较复杂，这里就不详细介绍了，大家可以参考相关论文。
** 小结
该题是一道最优化的问题，尝试发现动态规划，贪心等算法都无从下手。但经过一步步的分析，思路渐渐清晰，在得到了若干重要不等式后，问题豁然开朗，是一道求最佳匹配的问题，可以用经典的KM 算法求解。
而在对不求方案的问题的研究中，不局限于直观的原图，而是从各个方向各个角度入手，构造不同的图，以展现题目各个方面的性质。也将算法复杂度由
()3O m ，优化到()2O n m ，再到()3O n ，使效率大大提高。
下表是对上文研究的几个算法的简单比较： 时间复杂度 空间复杂度 算法核心
算法一
()3O m ()2O m KM 算法求最大权最大匹配
算法二
()22O n m
()O nm 用bellman_ford 算法求网络最大费用最大流增广路 算法三
()2O n m
()O nm 用SPF A 算法求网络最大费用最大流增广路
算法四
()3O n
()O nm
求结点带权的二分图的最小权匹配
四总结
通过对以上的例题的分析可见，在信息学竞赛中，二分图匹配算法的应用往往不是显而易见的，而是需要挖掘出问题的本质，从而构造合适的二分图并用匹配算法来求解。而在求匹配的时候往往也不是简单的套用经典算法，而是需要充分利用题目的特有性质，将经典匹配算法加以变形，从而得到更高效的算法。
信息学竞赛中的各种题目，往往都需要通过对题目的仔细观察，构造出合适的数学模型，然后通过对题目以及模型的进一步分析，挖掘出问题的本质，进行大胆的猜想，转化模型，设计合适的算法解决问题。
[感谢]
衷心感谢向期中老师在学习上对我的指导和帮助
衷心感谢任恺、胡伟栋和周源同学对我的大力帮助
衷心感谢肖湘宁和周戈林两位同学对我的论文提出宝贵的意见
[参考文献]
[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 c i 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 d i 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, |c i-d i|) 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 a i, b i and c i each —the numbers of the cities the road connects (1 ≤ a i≤ N, 1 ≤ b i≤ N, a i≠ b i) and the cost of maintaining it (1 ≤ c i≤ 10 000).
Output
Output M lines — for each road output d i 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
Ku二分图最大权匹配(KM算法)hn
Maigo的KM算法讲解(的确精彩) 顶点Ｙｉ的顶标为B［i]，顶点Xi与Yj之间的边权为w[ｉ,j]。在算法执行过程中的任一时刻，对于任一条边(ｉ,j),A［i]+B[j]>=w［i,ｊ]始终成立。KM 算法的正确性基于以下定理： * 若由二分图中所有满足A［i］+B[j]=ｗ[ｉ,ｊ］的边（i，ｊ)构成的子图（称做相等子图）有完备匹配,那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图,那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图,那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A［ｉ]＋B[j]>=w[i,j]恒成立,令A[i]为所有与顶点Xi关联的边的最大权，Ｂ[ｊ］＝0。如果当前的相等子图没有完备匹配,就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了,是因为对于某个Ｘ顶点,我们找不到一条从它出发的交错路。这时我们获得了一棵交错树,它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值ｄ,Y顶点的顶标全都增加同一个值d，那么我们会发现：
两端都在交错树中的边(i，j）,A［i]+B[j]的值没有变化。也就是说,它原来属于相等子图，现在仍属于相等子图。 两端都不在交错树中的边(ｉ，ｊ)，A[i］和B[j]都没有变化。也就是说,它原来属于(或不属于)相等子图，现在仍属于(或不属于)相等子图。 X端不在交错树中，Y端在交错树中的边(i，ｊ)，它的Ａ［ｉ]+B[j]的值有所增大。它原来不属于相等子图,现在仍不属于相等子图。 X端在交错树中,Ｙ端不在交错树中的边（i,j),它的A［ｉ]+B[j]的值有所减小。也就说,它原来不属于相等子图，现在可能进入了相等子图,因而使相等子图得到了扩大。 现在的问题就是求d值了。为了使Ａ[i]+Ｂ[j］>=w［i,ｊ]始终成立,且至少有一条边进入相等子图,d应该等于mｉｎ{Ａ[i]+B[ｊ]-w[ｉ,j]｜Xｉ在交错树中,Ｙi不在交错树中｝。 以上就是KＭ算法的基本思路。但是朴素的实现方法，时间复杂度为 O(n4)——需要找O(n)次增广路,每次增广最多需要修改Ｏ(n)次顶标,每次修改顶标时由于要枚举边来求d值,复杂度为O(ｎ2)。实际上KＭ算法的复杂度是可以做到O(n3)的。我们给每个Ｙ顶点一个“松弛量”函数slaｃk，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中,检查边(i,j)时，如果它不在相等子图中，则让ｓlaｃk[j]变成原值与A[i］+B[ｊ］-w[i,j]的较小值。这样,在修改顶标时，取所有不在交错树中的Y顶点的slacｋ值中的最小值作为ｄ值即可。但还要注意一点：修改顶标后，要把所有的ｓｌａｃk值都减去d。
二分图匹配(匈牙利算法和KM算法)
前言： 高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看KM的Pascal代码，大概知道过程了，后来老师说不是重点，所以忘的差不多了。都知道二分图匹配是个难点，我这周花了些时间研究了一下这两个算法，总结一下 1.基本概念 M代表匹配集合 未盖点：不与任何一条属于M的边相连的点 交错轨：属于M的边与不属于M的边交替出现的轨（链） 可增广轨：两端点是未盖点的交错轨 判断M是最大匹配的标准：M中不存在可增广轨 2.最大匹配，匈牙利算法 时间复杂度：O(|V||E|) 原理： 寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。修改M 为M&P。即这条轨进行与M进行对称差分运算。 所谓对称差分运算，就是比如X和Y都是集合，X&Y=(X并Y)-(x交Y) 有一个定理是：M&P的边数是|M|+1，因此对称差分运算扩大了M 实现： 关于这个实现，有DFS和BFS两种方法。先列出DFS的代码，带注释。这段代码来自中山大学的教材
核心部分在dfs(x)，来寻找可增广轨。如果找到的话，在Hungarian()中，最大匹配数加一。这是用了刚才提到的定理。大家可以想想初始状态是什么，又是如何变化的 view plaincopy to clipboardprint?
第二种方法BFS，来自我的学长cnhawk 核心步骤还是寻找可增广链，过程是： 1.从左的一个未匹配点开始，把所有她相连的点加入队列 2.如果在右边找到一个未匹配点，则找到可增广链 3.如果在右边找到的是一个匹配的点，则看它是从左边哪个点匹配而来的，将那个点出发的所有右边点加入队列 这么说还是不容易明白，看代码吧
二分图理论
图7-55二部图示例显然，在完全二部图中中，顶点数，边数。,r s K n r s =+m rs =一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图7-56可改画成图。可以看出，它们仍是二部图。)()d 图7-56二部图示例、管路敷设技术通过管线敷设技术不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标高等，要求技术交底。管线敷设技术中包含线槽、管架等多项式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故
算法学习：图论之二分图的最优匹配(KM算法)
二分图的最优匹配（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]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1->y4这条边） 现在的问题就是求d值了。为了使A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于： Min{A[i]+B[j]-w[i,j] | Xi在交错树中，Yi不在交错树中}。 改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y 顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }
二分图匹配
二分图匹配 1.最大匹配（hdu1068） Girls and Boys Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6410 Accepted Submission(s): 2888 Problem Description the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set. The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description: the number of students the description of each student, in the following format student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ... or student_identifier:(0) The student_identifier is an integer number between 0 and n-1, for n subjects. For each given data set, the program should write to standard output a line containing the result. Sample Input 7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3
二分图的最大匹配完美匹配和匈牙利算法
二分图的最大匹配完美匹配和匈牙利算法 匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是二部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。这篇文章讲无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于求解匹配的匈牙利算法（Hungarian Algorithm）；不讲带权二分图的最佳匹配。二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集U 和V ，使得每一条边都分别连接U、V 中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。图 1 是一个二分图。为了清晰，我们以后都把它画成图 2 的形式。匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，图3、图4 中红色的边就是图 2 的匹配。我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。例如图 3 中1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。最大匹配：一个图所有匹配中，所含匹
配边数最多的匹配，称为这个图的最大匹配。图 4 是一个最大匹配，它包含4 条匹配边。完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。基本概念讲完了。求解最大匹配问题的一个算法是匈牙利算法，下面讲的概念都为这个算法服务。交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图5 中的一条增广路如图6 所示（图中的匹配点均用红色标出）：增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数
图论专题 二分图
图论专题二分图 朝花夕拾2010-12-28 17:56:46 阅读66 评论0 字号：大中小订阅 二分图：二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联的两个顶点恰好一个属于集合X，另一个属于集合Y。 二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 最大匹配：图中包含边数最多的匹配称为图的最大匹配。 完美匹配：如果所有点都在匹配边上，则称这个最大匹配是完美匹配。 二分图匹配基本概念： 未盖点 设VI是G的一个顶点，如果VI不与任意一条属于匹配M的边相关联，就称VI是一个未盖点。 交错轨 设P是图G的一条轨，如果P的任意两条相邻的边一定是一条属于M而另一条不属于M，就称P是交错轨。 可增广轨（增广路） 两个端点都是未盖点的交错轨称为可增广轨。 可增广轨的性质： 1：P的路径长度必定为奇数，第一条边和最后一条边都不属于M。 2：P经过取反操作可以得到一个更大的匹配M’。 3：M为G的最大匹配当且仅当不存在相对于M的增广路径。 二分图最大匹配匈牙利算法： 算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"取反",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路。 代码： //匈牙利算法复杂度o(nm) #include
二分图的最大匹配经典之匈牙利算法
Doctor的图论计划之——二分图最大匹配 第一讲二分图的最大匹配经典之匈牙利算法 二分图，顾名思义就是分成了两个部分的图……很白痴的解释（自己吐槽了先），但吐槽的同时我们也要发现一些二分图的基本性质！ 性质1 二分图之所以分成了两个部分，那是因为单独的一个部分中的任意两点不连通！ 性质2 二分图匹配——匈牙利算法中我们只需记录集合1到集合2的单向边就可以了（注意看上边的图，箭头是单向的）思考这是为什么！ 但是！二分图确实是无向图！！！只不过匈牙利算法只是从一个集合另一个集合走一遍罢了！！！！ 性质3 树是一种特殊的二分图！ 紫色的结点构成集合1，绿色的结点构成集合2，换句话说，儿子和爸爸打仗时爷爷和
孙子站在同一战线！（也可以认为是儿子和爸妈吵架时总是爷爷奶奶护着，小时候有这样的记忆没有？反正我没有！） PS：树就是无回路懂不？ 性质3 对于任意二分图，其包含的环一定全部是偶环！（充要可证） 可以证明，含有奇数条边的环一定有两个在相同集合内的点有边相连！ 也就是说——二分图的bfs子树一定不含奇环！ 接下来说一下二分图求最大匹配的算法——匈牙利算法 【例1】传说中的多米诺骨牌覆盖问题 在一个n*m的棋盘上，摆放一些1*2大小的多米诺骨牌，但棋盘某些地方是坏 掉的，即不能将骨牌置于这些坏掉的格子上，求最多能摆上的骨牌数量 【例2】传说中的猎人打鸟问题 猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟都被 打掉，也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光 所有的鸟？ 【例3】传说中的搞对象问题 一保守教师想带学生郊游, 却怕他们途中谈恋爱,他认为满足下面条件之一的两 人谈恋爱几率很小: (1)身高差>40 (2) 性别相同(3) 爱好不同类型的音乐(4) 爱好同类型的运动 告诉你每个同学的信息，问老师最多能带多少学生？ 这样的问题如何解决？搜索？怎么搜？会不会超时？答案很简单，三道题中的元素都可以用很简单的方式分成两个互不相干的部分，因此可以用二分图匹配来解决这个问题：形象的说，我们规定搞基和百合都是不允许的，已知一群男人和女人，他们可以看做图中的顶点，男人构成了集合A,女人构成了集合B，边表示这名男人和这名女人互相有好感（可以配成一对）不考虑个人因素，现在希望为这些饥渴的男男女女找到最多的配对数（脚踏两只船也是不允许的！）为了解决这样的问题我们才引入了二分图的匹配算法——匈牙利算法！ 匈牙利算法是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出，因而得名。 如果暴搜的话那么无疑时间复杂度将成为O（2^E）！无法快速实现，于是我们就提出了更为高效的算法，这种算法是从网络流演变而来，但这里我们抛开所有网络流的知识，但从这一算法的角度来进行阐释！ 解释一些常用的名词 交错轨：所谓交错轨，还有一种更为文雅的说法叫增广轨，这种说法让人不禁联想到蛋疼的网络流算法，所以我更喜欢用一种与网络流无关的说法来称呼它，下面我们来举几个交错轨的例子：
用匈牙利算法求二分图的最大匹配
用匈牙利算法求二分图的最大匹配 什么是二分图，什么是二分图的最大匹配，这些定义我就不讲了，网上随便都找得到。二分图的最大匹配有两种求法，第一种是最大流（我在此假设读者已有网络流的知识）；第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。匈牙利算法其实很简单，但是网上搜不到什么说得清楚的文章。所以我决定要写一下。 最大流算法的核心问题就是找增广路径（augment path）。匈牙利算法也不例外，它的基本模式就是： 初始时最大匹配为空 while 找得到增广路径 do 把增广路径加入到最大匹配中去 可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性，下面我来分析一下。 （注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。每条边也不需要有方向。） 图1是我给出的二分图中的一个匹配：［1，5］和［2，6］。图2就是在这个匹配的基础上找到的一条增广路径：3->6->2->5->1->4。我们借由它来描述一下二分图中的增广路径的性质： (1)有奇数条边。 (2)起点在二分图的左半边，终点在右半边。 (3)路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。） (4)整条路径上没有重复的点。 (5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。） (6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。） (7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中
二分图最大匹配算法的应用及Matlab实现+++
一共有RecuCal.m LockMap.m BuildMatrix.m Edmonds.m GUI1.m 这几个文件，我把它们合到一块粘上去了,你再把他们分开保存就可以了. 其中前三个文件都是为建立邻接矩阵服务的，Edmonds.m是匈牙利算法的主文件，GUI1.m只是调用Edmonds.m做个界面而已。 调用关系是GUI1.m调用Edmonds.m；Edmonds.m调用BuildMatrix.m和LockMap.m ；LockMap.m调用RecuCal.m 最后运行GUI1.m就ok了 #LockMap.m function [LMA, LMB] = LockMap(n, m) % LOCKMAP - 求解满足条件锁并设置相应的映射 % 输入参数:n 表槽数,m 表高度数。 % 输出参数:LMA,LMB 分别为二维矩阵表示自然数到满足条件锁之间的映射。 global jiA ouB ary A B mm N N = n; mm = m; jiA=0; ouB=0; A=[]; B=[]; ary = zeros(1, n); RecuCal(n); LMA=A; LMB=B; [lena, n] = size(LMA); [lenb, n] =size(LMB); if lena>lenb temp = LMA; LMA=LMB;LMB=temp; temp = lena;lena=lenb;lenb=temp; end #RecuCal.m function RecuCal(n) % RECUCAL - 递归函数 global jiA ouB ary A B mm N if n ==1 for k=1:mm % 调用递归函数时要用到的变量所以 % 设为全局 ary(1) = k; Max = max(ary); Min = min(ary); num = 0; neighbor = 0; for i=1:N num = num + (Max-ary(i))*(ary(i)-Min);
Ku二分图最大权匹配(KM算法)hn
Kuhn-Munkres 算法
Maigo 的 KM 算法讲解（的确精彩）
KM 算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转 化为求完备匹配的问题的。设顶点 Xi 的顶标为 A[i]，
顶点 Yi 的顶标为 B[i]，顶点 Xi 与 Yj 之间的边权为 w[i,j]。在算法执行过程中 的任一时刻，对于任一条边(i,j)， A[i]+B[j]>=w[i,j]始终成立。KM 算法的正确 性基于以下定理： * 若由二分图中所有满足 A[i]+B[j]=w[i,j]的边(i,j)构成的子图 （称做相等子 图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相 等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相 等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配 一定是二分图的最大权匹配。 初始时为了使 A[i]+B[j]>=w[i,j]恒成立，令 A[i]为所有与顶点 Xi 关联的边 的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改 顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个 X 顶点，我们 找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点 全部是 X 顶点。现在我们把交错树中 X 顶点的顶标全都减小某个值 d，Y 顶 点的顶标全都增加同一个值 d，那么我们会发现：
两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于 相等子图，现在仍属于相等子图。 两端都不在交错树中的边(i,j)，A[i]和 B[j]都没有变化。也就是说，它原来属于 （或不属于）相等子图，现在仍属于（或不属于）相等子图。 X 端不在交错树中，Y 端在交错树中的边(i,j)，它的 A[i]+B[j]的值有所增大。 它原来不属于相等子图，现在仍不属于相等子图。 X 端在交错树中，Y 端不在交错树中的边(i,j)，它的 A[i]+B[j]的值有所减小。 也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子 图得到了扩大。 现在的问题就是求 d 值了。为了使 A[i]+B[j]>=w[i,j]始终成立，且至少有 一条边进入相等子图，d 应该等于 min{A[i]+B[j]-w[i,j]|Xi 在交错树中，Yi 不在 交错树中}。 以上就是 KM 算法的基本思路。但是朴素的实现方法，时间复杂度为 O(n4)——需要找 O(n)次增广路，每次增广最多需要修改 O(n)次顶标，每次 修改顶标时由于要枚举边来求 d 值，复杂度为 O(n2)。实际上 KM 算法的复 杂度是可以做到 O(n3)的。我们给每个 Y 顶点一个“松弛量”函数 slack，每次 开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如 果它不在相等子图中， 则让 slack[j]变成原值与 A[i]+B[j]-w[i,j]的较小值。 这样， 在修改顶标时，取所有不在交错树中的 Y 顶点的 slack 值中的最小值作为 d 值即可。但还要注意一点：修改顶标后，要把所有的 slack 值都减去 d。
二分图及二分图匹配
9.1 二 分 图 9.1.1 二分图的基本概念 定义9.1 无向图G =
证 先证必要性。 设G为二分图
二分图最大匹配及常用建图方法
算法———艺术 二分图匹配剖析 很多人说，算法是一种艺术。但是对于初学者的我，对算法认识不是很深刻，但偶尔也能感受到他强大的魅力与活力。这让我追求算法的脚步不能停止。下面我通过分析匈牙利算法以及常用建图方式，与大家一起欣赏算法的美。 匈牙利算法 匈牙利算法是用来解决最大二分图匹配问题的，所谓二分图即“一组点集可以分为两部分，且每部分内各点互不相连，两部分的点之间可以有边”。所谓最大二分图匹配即”对于二分图的所有边，寻找一个子集，这个子集满足两个条件， 1：任意两条边都不依赖于同一个点。 2：让这个子集里的边在满足条件一的情况下尽量多。首先可以想到的是，我们可以通过搜索，找出所有的这样的满足上面条件的边集，然后从所有的边集中选出边数最多的那个集合，但是我们可以感觉到这个算法的时间复杂度是边数的指数级函数，因此我们有必要寻找更加高效的方法。目前比较有效的方法有匈牙利算法和通过添加汇点和源点的网络流算法，对于点的个数都在200 到300 之间的数据，我们是采取匈牙利算法的，因为匈牙利算法实现起来要比网络流简单些。下面具体说说匈牙利算法：介绍匈牙利之前，先说说“增广轨”。 定义： 若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边 和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的 一条增广轨 定义总是抽象的下面通过图来理解它。 图中的线段（2->3, 3->1, 1->4）便是上面所说的p路径， 我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配 的边，则边（4,1）边（1,3）和边（3,2）在路径p上交 替的出现啦，那么p就是相对于M的一条增广轨，这样我 们就可以用边1,4 和边2,3来替换边1,3 那么以匹配的边 集数量就可以加1,。
二分图匹配算法及其应用【文献综述】
文献综述 数学与应用数学 二分图匹配算法及其应用 图的匹配理论简单的说就是使得图G 中每两个点之间都有联系. 匹配理论是图论中的一个重要内容, 它在运筹学、系统工程中都有着广泛的应用, 近几十年来, 随着组合数学的迅速发展, 匹配理论成为许多重要理论的基础和源泉. 二分图的最大匹配算法是匹配理论研究的热点之一. KM 算法是求最大匹配的经典算法, 它是在匈牙利算法的进一步提高, 它是解决数学中一类存在性问题的基本工具, 广泛应用于社会、经济、科技、自然等各个领域中. 本文主要研究KM 算法的具体原理, 步骤, 以及它一些实际问题中的应用. 图的匹配问题起源于1935年霍尔的“婚姻问题”. KM 算法是Kuhn 和Munkras 分别于1955年和1957年独立提出来的, 他们在研究图论中最大权匹配问题时很巧妙运用KM 算法去解决问题. 定义1 图G 有三部分所组成 (1) 非空集合)(G V , 称为G 的结点集, 其成员称为结点或顶点. (2) 集合)(G E , 称为G 的边集, 其成员称为边. (3) 函数 ))(),(()(:G V G V G E G →ψ, 称为边和顶点的关联映射. 这里))(),((G V G V 称为)(G V 的偶对集, 其成员偶对形如),(v u , u ,v 为结点, 它们未必不同. 当),()(v u e G =ψ时, 称边e 关联端点u ,v . 当),(v u 用作序偶时 )()())(),((G V G V G V G V ?=, e 称为有向边, e 以u 为起点, 以v 为终点, 图G 称为有向图; 当),(v u 用作无序偶对时, ),(),(u v v u =, 称e 为无向边(或边), 图G 称为无向图(或图). 定义2 无向图?ψ?=,,E V G 称为二分图, 如果有非空集合X ,Y 使
二分图
二分图 二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 1定义 简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集。 2辨析示例 区别二分图，关键是看点集是否能分成两个独立的点集。 上图中U和V构造的点集所形成的循环圈不为奇数，所以是二分图。
上图中U和V和W构造的点集所形成的的循环圈为奇数，所以不是二分图。 3必要条件 无向图G为二分图的充分必要条件是，G至少有两个顶点，且其所有回路的长度均为偶数。 证先证必要性。 设G为二分图
二分图的匹配.
第九章二分图中的匹配 三个典型问题： （1）在一个有禁止位置的m×n棋盘上，能放置非攻击型车的最多个数是多少？ （2）在一个有禁止位置的m×n棋盘上，能放置多米诺牌覆盖的最多个数是多少？ （3）一个公司有n个工作空缺，需要有一定技能的人填补，同时有m个人申请这些项工作，每人能胜任n项工作中的若干项，问最多有多少项工作能找到合适的 人选？ 9.1 一般的问题描述 定义1： 令X={x1, x2, …,x m}, Y={y1,y2, …,y n},且X∩Y＝Ф，而△是序偶e=(x,y)的集合，其中x ∈X,y∈Y,那么三元组G＝（X，△，Y）称作二分图。 定义2： 令G＝（X，△，Y）是一个二分图，边集△的子集M，若M中没有两条边存在公共点，称M是二分图G的一个匹配。 定义3： 设G是一个二分图，定义ρ（G）＝{∣M∣:M是G的一个匹配}为二分图G的最大匹配边数。 9.2 匹配 定义1： G＝（X，△，Y），X={x1, x2, …,x m}, Y={y1,y2, …,y n}，满足∣M*∣=ρ（G）的匹配M*称为二分图G的最大匹配。一般M*不唯一，且∣M*∣=ρ（G）≤min{m,n}。 寻找M*的困难点： （1）若已知ρ（G），那么遍历所有可能的匹配会找到M*，但搜索量巨大； （2）一般ρ（G）并不事先知道，要找到M*，并求出ρ（G）＝∣M*∣难度更大。 定义2： 令u和v是二分图G＝（X，△，Y）的任意两个顶点，连接u和v的互异顶点序列：γ：u=u0, u1, u2, …, u p-1, u p=v 使得任意两个相邻顶点有一条边连接，即：{ u0, u1},{ u1, u2},…, { u p-1, u p}∈△,那么称序列γ为二分图G的一个链。链长等于序列的边数p，若u=v, 链γ也叫圈。 定义3： 令M为二分图G＝（X，△，Y）中的一个匹配，令M是M的补集，即G的不属于M的边集合，M∪M＝△。令u和v是顶点，且u和v一个是左顶点（即属于X），一个是右顶点（即属于Y），若连接u和v的链满足下列性质： （1）γ的第一、三、五、、、边属于M；
二分图匹配模板.
1、图论—匹配 4。1 二分图最大匹配(hungary邻接表) //二分图最大匹配,hungary算法,邻接表形式,复杂度O(m*e) //返回最大匹配数,传入二分图大小m,n和邻接表list(只需一边) //match1,match2返回一个最大匹配,未匹配顶点match值为-1 #include
二分图详解
二分图大讲堂——彻底搞定最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配 文本内容框架： §1图论点、边集和二分图的相关概念和性质 §2二分图最大匹配求解 匈牙利算法、Hopcroft-Karp算法 §3二分图最小覆盖集和最大独立集的构造 §4二分图最小路径覆盖求解 §5二分图带权最优匹配求解 Kuhn-Munkers算法 §6小结 每章节都详细地讲解了问题介绍，算法原理和分析，算法流程，算法实现四部分内容，力求彻底解决问题。 §1图论点、边集和二分图的相关概念和性质 点覆盖、最小点覆盖 点覆盖集即一个点集，使得所有边至少有一个端点在集合里。或者说是“点”覆盖了所有“边”。。极小点覆盖(minimal vertex covering)：本身为点覆盖，其真子集都不是。最小点覆盖(minimum vertex covering)：点最少的点覆盖。点覆盖数(vertex covering number)：最小点覆盖的点数。 边覆盖、极小边覆盖 边覆盖集即一个边集，使得所有点都与集合里的边邻接。或者说是“边”覆盖了所有“点”。极小边覆盖(minimal edge covering)：本身是边覆盖，其真子集都不是。最小边覆盖(minimum edge covering)：边最少的边覆盖。边覆盖数(edge covering number)：最小边覆盖的边数。 独立集、极大独立集 独立集即一个点集，集合中任两个结点不相邻，则称V为独立集。或者说是导出的子图是零图（没有边）的点集。极大独立集(maximal independent set)：本身为独立集，再加入任何点都不是。最大独立集(maximum independent set)：点最多的独立集。独立数(independent number)：最大独立集的点。 团 团即一个点集，集合中任两个结点相邻。或者说是导出的子图是完全图的点集。极大团(maximal clique)：本身为团，再加入任何点都不是。最大团(maximum clique)：点最多的团。团数(clique number)：最大团的点数。 边独立集、极大边独立集 边独立集即一个边集，满足边集中的任两边不邻接。极大边独立集(maximal edge independent set)：本身为边独立集，再加入任何边都不是。最大边独立集(maximum edge independent set)：