二分图最佳带权匹配

二分图最佳带權匹配问题是指在给定带权二分图上求出一个最大匹配的问题，使得所有匹配边权值之和最大。这个问题也被称为二分图最优匹配。

此类问题通常使用KM算法或转换为一个网络费用流问题进行求解。

定义

一个带权二分图 $G=(X,Y,E)$ 中的边 $(u,v)\in E$ 都带有一个权值 $f(u,v)$。该二分图的一个最佳带权匹配是它所有匹配中，所有匹配边权值之和中最大的一个。

求解方法

KM算法

直接使用KM算法求解。

最小费用最大流

通过建立模型，使用费用流算法解决。

参考程序

C++

#include <cstdio>
#include <string.h>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int const MAX = 1000;
int const inf = INT_MAX;

int w[MAX][MAX];
int link[MAX];//代表当前与Y集合中配对的X集合中的点
int visx[MAX], visy[MAX];
int lx[MAX], ly[MAX];
int n, m;//代表X和Y中元素的个数
 
int can(int t)
{
    visx[t] = 1;
    for(int i = 1; i <= m; i++){
        if(!visy[i] && lx[t] + ly[i] == w[t][i]){//这里“lx[t]+ly[i]==w[t][i]”决定了这是在相等子图中找增广路的前提，非常重要
            visy[i] = 1;
            if(link[i] == -1 || can(link[i])){
                link[i] = t;
                return 1;
            }
        }
    }
    return 0;
}

int km(void)
{
    int sum = 0; memset(ly, 0, sizeof(ly));
    for(int i = 1; i <= n; i++){//把各个lx的值都设为当前w[i][j]的最大值
        lx[i] = -inf;
        for(int j = 1; j <= n; j++){
            if(lx[i] < w[i][j])
                lx[i] = w[i][j];
        }
    }

    memset(link, -1, sizeof(link));
    for(int i = 1; i <= n; i++){
        while(1){
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if(can(i))//如果它能够形成一条增广路径，那么就break
                break;
            int d = inf;//否则，后面应该加入新的边,这里应该先计算d值
            for(int j = 1; j <= n; j++)//对于搜索过的路径上的XY点，设该路径上的X顶点集为S，Y顶点集为T，对所有在S中的点xi及不在T中的点yj
                if(visx[j])
                    for(int k = 1; k <= m; k++)
                       if(!visy[k])
                            d = min(d, lx[j] + ly[k] - w[j][k]);
            if(d == inf)
            return -1;//找不到可以加入的边，返回失败（即找不到完美匹配）
            for (int j = 1; j <= n; j++)
                if (visx[j])
                    lx[j] -= d;
            for(int j = 1; j <= m; j++)
                if(visy[j])
                    ly[j] += d;
            }
    }
    for(int i = 1; i <= m; i++)
        if(link[i] > -1)
            sum += w[link[i]][i];
    return sum;
}