求带边权2分图的最大匹配.doc

求二部图的最大权匹配的两个算法一、 求最大权二分匹配的KM算法/%e6%b1%82%e6%9c%80%e5%a4%a7%e6%9d%83%e4%ba%8c%e5%88%86%e5%8c%b9%e9%85%8d%e7%9a%84km%e7%ae%97%e6%b3%95/最大权二分匹配问题就是给二分图的每条边一个权值，选择若干不相交的边，得到的总权值最大。解决这个问题可以用KM算法。理解KM算法需要首先理解“可行顶标”的概念。可行顶标是指关于二分图两边的每个点的一个值lxi或lyj，保证对于每条边wij都有lxi+lyj-wij=0。如果所有满足lxi+lyj=wij的边组成的导出子图中存在一个完美匹配，那么这个完美匹配肯定就是原图中的最大权匹配。理由很简单：这个匹配的权值之和恰等于所有顶标的和，由于上面的那个不等式，另外的任何匹配方案的权值和都不会大于所有顶标的和。但问题是，对于当前的顶标的导出子图并不一定存在完美匹配。这时，可以用某种方法对顶标进行调整。调整的方法是：根据最后一次不成功的寻找交错路的DFS，取所有i被访问到而j没被访问到的边(i,j)的lxi+lyj-wij的最小值d。将交错树中的所有左端点的顶标减小d，右端点的顶标增加d。经过这样的调整以后：原本在导出子图里面的边，两边的顶标都变了，不等式的等号仍然成立，仍然在导出子图里面；原本不在导出子图里面的边，它的左端点的顶标减小了，右端点的顶标没有变，而且由于d的定义，不等式仍然成立，所以他就可能进入了导出子图里。初始时随便指定一个可行顶标，比如说lxi=maxwij|j是右边的点，lyi=0。然后对每个顶点进行类似Hungary算法的find过程，如果某次find没有成功，则按照这次find访问到的点对可行顶标进行上述调整。这样就可以逐步找到完美匹配了。值得注意的一点是，按照上述d的定义去求d的话需要O(N2)的时间，因为d需要被求O(N2)次，这就成了算法的瓶颈。可以这样优化：设slackj表示右边的点j的所有不在导出子图的边对应的lxi+lyj-wij的最小值，在find过程中，若某条边不在导出子图中就用它对相应的slack值进行更新。然后求d只要用O(N)的时间找到slack中的最小值就可以了。如果是求最小权匹配，只需要把那个不等式反一下就行了。算法需要作出的改变是：lx的初值为所有临界边中的最小值，find中t反号。示例程序(Ural 1076)：/dd-usaco/cpp/ural1076.cpp二、求带边权2分图的最大匹配【/article-show-13566.html】 输入正整数N,然后是N*N个正整数，表示边权邻接矩阵。coldfusion 输出求解过程。 /* Problem : Weighted Bipartite Matching Algorithm : Hungarian Algorithm Reference : Douglas B.West,Introduction to Graph Theory,125-129 Author : PC Date : 2005.2.23 */ #include #include #include #include ifstream fin(input.txt); #define cin fin const int max=50; bool Tmax,Rmax,visitedmax; int Umax,Vmax,gtmaxmax,xmax,ymax; int N; void output() int i,j; for(i=0;iN;i+) for(j=0;jN;j+) coutsetw(2)gtij ; if(Ri)coutsetw(2)R ; coutendl; for(i=0;iN;i+) if(Ti)coutsetw(2)T ; else coutsetw(2) ; coutendl; int path(int u) int v; for(v=0;vN;v+) if(gtuv=0 & !visitedv) visitedv=1; if(yvN;) int i,j,ans,sigma,step=0; for(i=0;iN;i+) Ui=Vi=0; for(j=0;jgtij; if(Uigtij)Ui=gtij; for(i=0;iN;i+) for(j=0;jN;j+) gtij=Ui-gtij; / for(;) ans=0; sigma=0; memset(x,-1,sizeof(x); memset(y,-1,sizeof(y); memset(R,0,sizeof(R); memset(T,0,sizeof(T); for(i=0;iN;i+) if(xi0) memset(visited,0,sizeof(visited); ans+=path(i); for(j=0;jN;j+) if(sigmagtij & gtij0) sigma=gtij; coutstep +step=N) break; for(i=0;iN;i+) if(!Ri) Ui-=sigma; if(Ti) Vi+=sigma; for(j=0;jN;j+) if(Tj) gtij+=sigma; if(!Ri) gtij-=sigma; / ans=0; coutResult:endl; for(i=0;iN;i+) ans+=Ui+Vi; for(j=0;jN;j+) if(xi=j & yj=i)coutsetw(2)Ui+Vj ; else coutsetw(2)0 ; coutendl; coutMaximum : ansendl; return 0; input.txt: 5 4 1 6 2 3 5 0 3 7 6 2 3 4 5 8 3 4 6 3 4 4 6 5 8 6 5 4 4 4 3 6 1 1 4 3 4 1