最優匹配：使二分圖的邊權和最大的完備匹配。（如果二分圖的兩個點集不相等可以通過加 ’點‘ 和 ’權值為0的邊‘ 實現轉化）
相關概念
可行頂標：若L(x)是頂點x對應的頂標值。可行頂標對於圖中的每條邊(x,y)都有L(x)+L(y)>=w(x,y)
相等子圖：只包含L(x)+L(y)=w(x,y)的邊的子圖
算法流程
設頂點Xi的頂標為a[i]，頂點Yi的頂標為b[i]
ⅰ.初始時，a[i]為與Xi相關聯的邊的最大權值，b[j]=0，保證a[i]+b[j]>=w(i,j)成立
ⅱ.當相等子圖中不包含完備匹配時，就適當修改頂標以擴大相等子圖，直到找到完備匹配為止
修改頂標的方法：當從 Xi 開始尋找交錯路失敗後，得到一棵交錯樹，對交錯樹中 X 頂點的頂標減少 d 值， Y 頂點的頂標增加 d 值。
對於圖中所有的邊 (i,j) 有：
i和j都不在交錯樹中，邊(i,j)仍然不屬於相等子圖
i和j都在交錯樹中，邊(i,j)仍然屬於相等子圖
i不在交錯樹中，j在交錯樹中，a[i]+b[j]擴大，邊(i,j)不屬於相等子圖
i在交錯樹,j不在交錯樹中,邊(i,j)有可能加入到相等子圖中
為了使a[i]+b[j]>=w(i,j)始終成立,且至少有一條邊加入到相等子圖中,d=min{a[i]+b[j]-w(i,j)},其中 i 在交錯樹中, j 不在交錯樹中。
由於在算法過程一直保持頂標的可行性，所以任意一個匹配的權值和肯定小於等於所有結點的頂標之和，又因為在擴大相等子圖過程中優先加入了權值大大邊，所以在相等子圖中找到的第一個完備匹配就是最優匹配。
[cpp]
include<stdio.h>
#include<string.h>
#define N 305
#define Max 1000000
int w[N][N],linky[N]; //數組 w 記錄邊權，數組 linky 記錄頂點 y 的匹配；
int lx[N],ly[N]; //數組 lx 和 ly 分別記錄頂點 x 和 y 的頂標值；
int visx[N],visy[N]; //數組 visx 和 visy 分別記錄頂點 x 和 y 是否被訪問；
int n,low; //low 記錄每次頂標需要變化的值；
int Find(int x)
{
int y,t;
visx[x]=1;
for(y=0;y<n;y++){
if(visy[y])continue;
t=lx[x]+ly[y]-w[x][y];
if(t==0){
visy[y]=1;
if(linky[y]==-1||Find(linky[y])){
linky[y]=x;
return 1;
}
}
else{
if(low>t)low=t;
}
}
return 0;
}
void KM()
{
int i,x;
for(x=0;x<n;x++){
while(1){
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
low=Max;
if(Find(x))break;
for(i=0;i<n;i++){
if(visx[i])
lx[i]-=low;
if(visy[i])
ly[i]+=low;
}
}
}
}
int main()
{
int i,j,sum;
while(scanf("%d",&n)!=EOF){
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(linky,-1,sizeof(linky));
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&w[i][j]);
if(lx[i]<w[i][j])
lx[i]=w[i][j];
}
}
KM();
for(i=0,sum=0;i<n;i++){
sum+=w[linky[i]][i];
}
printf("%d\n",sum);
}
return 0;
}
