《求带边权2分图的最大匹配.doc》由会员分享，可在线阅读，更多相关《求带边权2分图的最大匹配.doc（5页珍藏版）》请在金锄头文库上搜索。
1、求二部图的最大权匹配的两个算法一、 求最大权二分匹配的KM算法http:/ 1076)：http:/ 输入正整数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 #includ
2、e 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
3、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+)
