这些都是刘汝佳的算法训练指南上的例题，基本包括了常见的几种二分图匹配的算法。

二分图是这样一个图，顶点分成两个不相交的集合X , Y中，其中同一个集合中没有边，所有的边关联在两个集合中。

给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

最大匹配：包含边数最多的匹配。

最小点覆盖 = 最大匹配数 最大独立集 = N - 最大匹配数 (与最小点覆盖互补)

最小路径覆盖 = N - 最大匹配数

UVa 1411 - Ants

问题可以转化成求最小权完美匹配，权值为黑点到白点的欧几里得距离。KM算法

[cpp]
/* **********************************************
Author : JayYe
Created Time: 2013-8-17 18:06:01
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
#include
using namespace std;

const double eps = 1e-6;

const int maxn = 100;

struct Point{
int x, y;
}a[maxn+10];

bool S[maxn+10], T[maxn+10]; // S表示在左边集合，T表示在右边集合
double lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10]; // 利用slack来松弛，时间复杂度降到O(n^3)
int match[maxn+10], n;

bool dfs(int u) {
S[u] = 1;
for(int i = 1;i <= n; i++) if(!T[i])
if(slack[i] - (w[u][i] - lx[u] - ly[i]) > eps)
slack[i] = w[u][i] - lx[u] - ly[i];
for(int i = 1;i <= n; i++) if(fabs(w[u][i] - lx[u] - ly[i]) < eps && !T[i]) {
T[i] = 1;
if(!match[i] || dfs(match[i])) {
match[i] = u;
return true;
}
}
return false;
}

void update() {
double delta = 1<<30;
for(int i = 1;i <= n; i++) if(!T[i] && delta - slack[i] > eps)
delta = slack[i];
for(int i = 1;i <= n; i++) {
if(S[i]) lx[i] += delta;
if(T[i]) ly[i] -= delta;
}
}

void KM() {
int i, j;
for(i = 1;i <= n; i++) {
lx[i] = 1<<30;
ly[i] = match[i] = 0;
// 与最大权完美匹配不同，最小权初始lx应该设为最小，每次update有最小增
for(j = 1;j <= n; j++) if(lx[i] - w[i][j] > eps)
lx[i] = w[i][j];
}

for(i = 1;i <= n; i++) {
while(true) {
for(j = 1;j <= n; j++) S[j] = T[j] = 0 , slack[j] = 1<<30;
if(dfs(i)) break;
else update();
}
}
}

void solve() {
int i, j, x, y;
for(i = 1;i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y);
for(i = 1;i <= n ;i++) {
scanf("%d%d", &x, &y);
for(j = 1;j <= n; j++)
w[i][j] = sqrt((a[j].x - x)*(a[j].x - x) + (a[j].y - y)*(a[j].y - y));
}
KM();
for(i = 1;i <= n; i++) printf("%d\n", match[i]);
}

int main() {
while(scanf("%d", &n) != -1) {
solve();
}
return 0;
}

/* **********************************************
Author : JayYe
Created Time: 2013-8-17 18:06:01
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
#include
using namespace std;

const double eps = 1e-6;

const int maxn = 100;

struct Point{
int x, y;
}a[maxn+10];

bool S[maxn+10], T[maxn+10]; // S表示在左边集合，T表示在右边集合
double lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10]; // 利用slack来松弛，时间复杂度降到O(n^3)
int match[maxn+10], n;

bool dfs(int u) {
S[u] = 1;
for(int i = 1;i <= n; i++) if(!T[i])
if(slack[i] - (w[u][i] - lx[u] - ly[i]) > eps)
slack[i] = w[u][i] - lx[u] - ly[i];
for(int i = 1;i <= n; i++) if(fabs(w[u][i] - lx[u] - ly[i]) < eps && !T[i]) {
T[i] = 1;
if(!match[i] || dfs(match[i])) {
match[i] = u;
return true;
}
}
return false;
}

void update() {
double delta = 1<<30;
for(int i = 1;i <= n; i++) if(!T[i] && delta - slack[i] > eps)
delta = slack[i];
for(int i = 1;i <= n; i++) {
if(S[i]) lx[i] += delta;
if(T[i]) ly[i] -= delta;
}
}

void KM() {
int i, j;
for(i = 1;i <= n; i++) {
lx[i] = 1<<30;
ly[i] = match[i] = 0;
// 与最大权完美匹配不同，最小权初始lx应该设为最小，每次update有最小增
for(j = 1;j <= n; j++) if(lx[i] - w[i][j] > eps)
lx[i] = w[i][j];
}

for(i = 1;i <= n; i++) {
while(true) {
for(j = 1;j <= n; j++) S[j] = T[j] = 0 , slack[j] = 1<<30;
if(dfs(i)) break;
else update();
}
}
}