首页 > 代码库 > Kuhn-Munkres算法。带权二分图匹配模板 (bin神小改版本)
Kuhn-Munkres算法。带权二分图匹配模板 (bin神小改版本)
/******************************************************二分图最佳匹配 (kuhn munkras 算法 O(m*m*n)).邻接矩阵形式 。 返回最佳匹配值,传入二分图大小m,n邻接矩阵 map ,表示权,m1,m2返回一个最佳匹配,为匹配顶点的match值为-1,一定注意m<=n,否则循环无法终止,最小权匹配可将全职取相反数。初始化: for(i=0;i<MAXN;i++) for(j=0;j<MAXN;j++) mat[i][j]=-inf;对于存在的边:mat[i][j]=val;//注意不能负值 ********************************************************/#define MAXN 15int n,m;int m1[MAXN];int m2[MAXN];bool isequal(double a,double b){ if(fabs(a-b)<0.00000001) return 1; return 0;}double km_match(int m,int n,double map[][MAXN]){ int s[MAXN],t[MAXN]; double l1[MAXN],l2[MAXN]; int p,q,i,j,k; double res=0; for(i=0;i<m;i++) { l1[i]=-10000000; for(j=0;j<n;j++) l1[i]=map[i][j]>l1[i]?map[i][j]:l1[i]; if(isequal(l1[i],-10000000)) return -1; } for(i=0;i<n;i++) l2[i]=0; memset(m1,-1,sizeof(m1)); memset(m2,-1,sizeof(m2)); for(i=0;i<m;i++) { memset(t,-1,sizeof(t)); p=0;q=0; for(s[0]=i;p<=q&&m1[i]<0;p++) { for(k=s[p],j=0;j<n&&m1[i]<0;j++) { if(isequal(l1[k]+l2[j],map[k][j])&&t[j]<0) { s[++q]=m2[j]; t[j]=k; if(s[q]<0) { for(p=j;p>=0;j=p) { m2[j]=k=t[j]; p=m1[k]; m1[k]=j; } } } } } if(m1[i]<0) { i--; double pp=10000000; for(k=0;k<=q;k++) { for(j=0;j<n;j++) { if(t[j]<0&&l1[s[k]]+l2[j]-map[s[k]][j]<pp) pp=l1[s[k]]+l2[j]-map[s[k]][j]; } } for(j=0;j<n;j++) l2[j]+=t[j]<0?0:pp; for(k=0;k<=q;k++) l1[s[k]]-=pp; } } for(i=0;i<m;i++) res+=map[i][m1[i]]; return res;}
Kuhn-Munkres算法。带权二分图匹配模板 (bin神小改版本)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。