UVa 二分图匹配 Examples

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

二分图是这样一个图，顶点分成两个不相交的集合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 <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
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 <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
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有

补充：软件开发 , C++ ,