二分图最佳匹配有匹配后总权值最大和最小两种，求最佳匹配的一个有效算法是KM算法。KM算法很复杂很费解。现在只能总结步骤。
KM算法步骤（ 以下有层次关系，㈠ > 1 > (1) > ① > Ⅰ）
(一) 建图：所有点分为两部分，一部分属于L端，一部分属于R端，两端的点各有n个，现在要为L端的所有点在R端的点中找它们的匹配，使最后总权值最大或最小，设有一条边联通L的i点与R的j点，权值为w[i][j]，设二维数组gragh_m保存图,graph_m[i][j]= w[i][j]。
(二) 为每个点设一个顶标，L端的为pl，R端的为pr，将pr的全赋为0，pl全赋为与这个点联通的权值最大的边的权值，例如与L端第i个联通的最大权值的边的权值为m，则pl[i]=m。
(三) 用一个循环枚举L中的每个点，为每个点在R中找其最佳匹配
1.设一辅助数组slack（可在全局定义）大小为n,将slack全赋为MAX_INT（无穷大）。
2、用一个死循环为L中的每个点找匹配，直到找到这个匹配时候break掉此循环，
⑴定义两个数组vl,vr，全赋为0，分别表示L中的某个点没有被访问过和R中的某个点没有被需要过（需要表示R中的某个点满足L中的某个点的最佳匹配要求，但被需要不表示最后能肯定配到它）
⑵以当前的为其找匹配的点作为实参调用匹配函数match，这里假定这个点位置为pos
match 函数体如下:
① 将vl[pos]赋为1（访问过…）
② 用个循环枚举R中的每个点，设当前点为j,如果这个点还没有被需要过（vr[j]==0）则执行：定义变量val=pl[pos]+pr[j]-graph_m[pos][j];
如果val==0(满足匹配条件)
{
Ⅰ.vr[j]=1;
Ⅱ.如果pre[j]==-1或者match（pre[j]）==1(pre[j]表示L中与R中j点的匹配点)，则pre[j]=pos，返回真。
}
否则如果（val>0）
{
如果val<slack[j],则slack[j]=val;
}
③返回假。
⑶．如果match返回真，break当前循环。
⑷定义变量d=MAX_INT,枚举R中每个点，如果vr[j]==0（没被访问过）并且slack[j]<val，则d赋值为slack[kj]。
⑸枚举L中每个点和R中每个点，假设当前点为j,如果vl[j]=1,则pl-=d；如果vr[j]==1,则pr[j]+=d;
3.将匹配后每个匹配对的权值加起来。
KM算法C++模板，模板的注释为上面所描述的步骤
最佳匹配题目
POJ2195 这里求的是最小匹配，模板的返回值要变成负的，代码