二分图最佳匹配的问题。值得一提的是，二分图的带权匹配与最佳匹配并不是一个概念。
什么是二分图的带权匹配？二分图的带权匹配就是求出一个匹配集合，使得集合中边的权值之和最大或最小。而二分图的最佳匹配则一定为完备匹配，在此基础上，才要求匹配的边权值之和最大或最小。二分图的带权匹配与最佳匹配不等价，也不互相包含。
首先我们可以明确，在这个问题上我们可以人为地添加源点与汇点，将问题转化为一个最大费用流的问题（见下参考2）。但耐不住KM写起来比较简单，且算法时间复杂度可以接受（$O(n^3)$）。
首先给出以下定义：
- 顶标：二分图两个子集的每个点都对应的一个标记，满足$el_{i}+er_{j}\geq w_{ij}$。
- 相等边：$el_{i}+er_{j}=w_{ij}$。
- 相等子图：相等边构成的子图。
- 交错树：增广路径形成的树。
对于KM算法，其目标是使每个相等子图完备匹配，从而得到整个二分图的最佳匹配。
具体的算法流程我们依旧可以用匈牙利算法讲解中惯用的找对象这个梗来理解。相较于匈牙利算法，我们通过顶标给了左右两方一个期望，当期望达不到时（即不存在相等边使其匹配），就调整其期望（松弛），重复以上操作使其全部匹配，我们就得到了二分图的最佳匹配。
参考代码（HDU2255）
#include <bits/stdc++.h>
using namespace std;
const int N = 301;
const int INF = 0x3F3F3F;
int n, m;
int G[N][N];
int match[N]; // 配对(储存左顶点)
int el[N], er[N]; // 顶标(储存期望)
bool vis_l[N], vis_r[N];
int slack[N]; // min(el[u] + er[v] - e[u][v]) 松弛量
bool search(int x) {
vis_l[x] = true;
for ( int y = 1; y <= n; ++y ) {
if ( vis_r[y] )
continue;
int temp = el[x] + er[y] - G[x][y];
if ( temp == 0 ) {
vis_r[y] = true;
if ( match[y] == -1 || search(match[y]) ) {
match[y] = x;
return true;
}
} else if ( slack[y] > temp)
slack[y] = temp;
}
return false;
}
int km() {
memset(match, -1, sizeof match);
memset(er, 0, sizeof er);
for ( int i = 1; i <= n; ++i ) {
el[i] = -INF;
for ( int j = 1; j <= n; ++j )
if ( G[i][j] > el[i] )
el[i] = G[i][j];
}
for ( int x = 1; x <= n; ++x ) {
for ( int i = 1; i <= n; ++i )
slack[i] = INF;
while ( true ) {
memset(vis_l, 0, sizeof vis_l);
memset(vis_r, 0, sizeof vis_r);
if ( search(x) )
break;
int d = INF;
for ( int i = 1; i <= n; ++i )
if ( !vis_r[i] && d > slack[i] )
d = slack[i];
for ( int i = 1; i <= n; ++i )
if ( vis_l[i] )
el[i] -= d;
for ( int i = 1; i <= n; ++i )
if ( vis_r[i] )
er[i] += d;
else
slack[i] -= d;
}
}
int ret = 0;
for ( int i = 1; i <= n; ++i )
if ( match[i] != -1 )
ret += G[match[i]][i];
return ret;
}
int main() {
while ( scanf("%d", &n) == 1 ) {
for ( int i = 1; i <= n; ++i )
for ( int j = 1; j <= n; ++j )
scanf("%d", &G[i][j]);
printf("%d\n", km());
}
return 0;
}