二分图匹配(匈牙利算法和KM算法).pdf

前言：高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看 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?1.#include 2.#define F(i,a,b)for(int i=a;i=b;i+)3.#define maxn 10024.using namespace std;5.bool mkmaxn,mapmaxnmaxn;6.int matchmaxn,n,m;7.bool dfs(int x)/寻找增广链,true 表示找到8.9.for(int i=1;i n m;39.int a,b;40.while(cin a b)41.42.mapab=true;43.44.cout hungarian()endl;45.F(i,1,m)46.if(matchi!=0)47.cout matchi i endl;48.return 0;49.50./*http:/ 553.1 154.1 255.2 256.2 357.3 258.3 559.4 360.5 361.5 462.5 563.out.txt64.565.剩下是匹配结果66.*/第二种方法 BFS，来自我的学长 cnhawk核心步骤还是寻找可增广链，过程是：1.从左的一个未匹配点开始，把所有她相连的点加入队列2.如果在右边找到一个未匹配点，则找到可增广链3.如果在右边找到的是一个匹配的点，则看它是从左边哪个点匹配而来的，将那个点出发的所有右边点加入队列这么说还是不容易明白，看代码吧view plaincopy to clipboardprint?1./匈牙利算法实现2.int Bipartite(bool vc MAX,int nv1,int nv2)3.4./vc为二分图，nv1,nv2 分别为左边的点数5.int i,j,x,n;6./n 为最大匹配数7.int qMAX,prevMAX,qs,qe;8./q 是 BFS 用的队列，prev 是用来记录交错链的，同时也用来记录右边的点是否被找过9.int vm1MAX,vm2MAX;10./vm1,vm2 分别表示两边的点与另一边的哪个点相匹配11.n=0;12.for(i=0;i nv1;i+)vm1i=-1;13.for(i=0;i nv2;i+)vm2i=-1;/初始化所有点为未被匹配的状态14.for(i=0;i nv1;i+)15.16.if(vm1i!=-1)continue;17./对于左边每一个未被匹配的点进行一次 BFS 找交错链18.for(j=0;j nv2;j+)prevj=-2;/表示刚进行过初始化19./每次 BFS 时初始化右边的点20.qs=qe=0;/初始化 BFS 的队列21./下面这部分代码从初始的那个点开始，先把它能找的的右边的点放入队列22./稍微改一下可以适用于用邻接表实现的二分图23.for(j=0;j nv2;j+)if(vcij)24.25.prevj=-1;26.qqe+=j;27.28./BFS29.while(qs qe)30.x=qqs;31.if(vm2x=-1)break;32./如果找到一个未被匹配的点，则结束，找到了一条交错链33.qs+;34./下面这部分是扩展结点的代码，稍微改一下可以适用于用邻接表实现的二分图35.for(j=0;j -1)46.47.vm1vm2prevx=x;48.vm2x=vm2prevx;49.x=prevx;50.51.vm2x=i;52.vm1i=x;53./匹配的边数加一54.n+;55.56.return n;57.3.最佳匹配最佳匹配加权图中，权值最大的最大匹配KM 算法：算法：概念：f(v)是每个点的一个值，使得对任意 u,v C V，f(u)+f(v)=w eu,v集合 H：一个边集，使得 H 中所有 u,v 满足 f(u)+f(v)=w eu,v等价子图：Gf(V,H)，标有 f 函数的 G 图理论：对于 f 和 Gf，如果有一个理想匹配集合 Mp，则 Mp最优。对于任意匹配集合 M，weight(M)weight(Mp)KM 算法的实质是扩展 Gf，直到找到理想的匹配集合伪代码view plaincopy to clipboardprint?1./S 是未匹配的顶点集2.while(M 不是 Mp)3.4./F(S)是 Gf 中与 S 中顶点相邻的顶点集5.if（F(S)=T）6.7.d=min(fu+fw-weightuw);/u in S,w not in T8.for each v in V9.10.if(v in S)11.fv=fv-d;12.else13.if(v in T)14.fv=fv-d;15.16.17.18.else/19.20.w=F(S)-T 中一个顶点21.if(w 未匹配)22.23.P 是刚找到的增大路径24.M=M 与 P 的对称差分运算结果25.S 是某个未匹配的顶点26.T=null27.28.else29.30.S=S+M 中 w 的相邻点31.T=T+w32.33.34.最后给一个代码，跟伪代码的思路不是很一样。从网上找的view plaincopy to clipboardprint?1.#include 2.#include 3.#include/使用其中的 min 函数4.using namespace std;5.const int MAX=1024;6.int n;/X 的大小7.int weight MAX MAX;/X 到 Y 的映射（权重）8.int lx MAX,ly MAX;/标号9.bool sx MAX,sy MAX;/是否被搜索过10.int match MAX;/Y(i)与 X(match i)匹配11./初始化权重12.void init(int size);13./从 X(u)寻找增广道路，找到则返回 true14.bool path(int u);15./参数 maxsum 为 true，返回最大权匹配，否则最小权匹配16.int bestmatch(bool maxsum=true);17.void init(int size)18.19./根据实际情况，添加代码以初始化20.n=size;21.for(int i=0;i n;i+)22.for(int j=0;j n;j+)23.scanf(%d,&weight i j);24.25.26.bool path(int u)27.28.sx u=true;29.for(int v=0;v n;v+)30.if(!sy v&lxu+ly v=weight u v)31.32.sy v=true;33.if(match v=-1|path(match v)34.35.match v=u;36.return true;37.38.39.return false;40.41.int bestmatch(bool maxsum)42.43.int i,j;44.if(!maxsum)45.46.for(i=0;i n;i+)47.for(j=0;j n;j+)48.weight i j=-weight i j;49.50./初始化标号51.for(i=0;i n;i+)52.53.lx i=-0 x1FFFFFFF;54.ly i=0;55.for(j=0;j n;j+)56.if(lx i weight i j)57.lx i=weight i j;58.59.memset(match,-1,sizeof(match);60.for(int u=0;u n;u+)61.while(1)62.63.memset(sx,0,sizeof(sx);64.memset(sy,0,sizeof(sy);65.if(path(u)66.break;67./修改标号68.int dx=0 x7FFFFFFF;69.for(i=0;i n;i+)70.if(sx i)71.for(j=0;j n;j+)72.if(!sy j)73.dx=min(lxi+ly j-weight i j,dx);74.for(i=0;i n;i+)75.76.if(sx i)77.lx i-=dx;78.if(sy i)79.ly i+=dx;80.81.82.int sum=0;83.for(i=0;i n;i+)84.sum+=weight match i i;85.if(!maxsum)86.87.sum=-sum;88.for(i=0;i n;i+)89.for(j=0;j n;j+)90.weight i j=-weight i j;/如果需要保持 weight 原来的值，这里需要将其还原91.92.return sum;93.94.95.int main()96.97.freopen(in.txt,r,stdin);98.int n;99.scanf(%d,&n);100.init(n);101.int cost=bestmatch(true);102.printf(%d n,cost);103.for(int i=0;i X%d n,i,match i);106.107.return 0;108.109./*110.5111.3 4 6 4 9112.6 4 5 3 8113.7 5 3 4 2114.6 3 2 2 5115.8 4 5 4 7116./执行 bestmatch(true)，结果为 29117.*/118./*119.5120.7 6 4 6 1121.4 6 5 7 2122.3 5 7 6 8123.4 7 8 8 5124.2 6 5 6 3125./执行 bestmatch(false)，结果为 21126.*/