二分图最佳匹配（
kuhn munkras
算法
O(m*m*n)
）
|
邻接距阵形式
,
复杂度
O(m*m*n)
返回最佳匹配值
,
传入二分图大小
m,n
|
邻接距阵
mat,
表示权
, match1,match2
返回一个最佳匹配
,
未匹配顶点
| match
值为
-1,
一定注意
m<=n,
否则循环无法终止
,
最小权匹配可将权值
|
取相反数
|
初始化：
for( i=0 ; i < MAXN ; ++i )
for( j=0 ; j < MAXN ; ++j ) mat[i][j] = -inf;
|
对于存在的边：
mat[i][j] = val ; //
注意，不能有负值
\*==================================================*/
#include
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,-1,sizeof(int)*MAXN)
int kuhn_munkras(int m,int n,int mat[][MAXN],int*
match1,int* match2){
int
s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i
for (l1[i]=-inf,j=0;j
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
if( l1[i] == -inf ) return -1;//
无法匹配！
}
for (i=0;i
for (_clr(match1),_clr(match2),i=0;i
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j
if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]<0){
for (i--,p=inf,k=0;k<=q;k++)
for (j=0;j
if
(t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j
for (k=0;k<=q;l1[s[k++]]-=p);
}
}
for (i=0;i
{// if
处理无匹配的情况！！
if( match[i] < 0 ) return -1;
if( mat[i][match[i]] <= -inf ) return -1;
ret+=mat[i][match1[i]];
}
return ret;
}