二分图的最佳完美匹配（模板）

54 阅读 0 评论 36 点赞

我是靠谱客的博主酷炫哈密瓜，最近开发中收集的这篇文章主要介绍二分图的最佳完美匹配（模板），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二分图的最佳完美匹配，也就是带权值的无向二分图中权值之和最大的完美匹配，整个图分为两个不相交的集合x和y，采用KM算法求解，也称匈牙利算法. 时间复杂度为O(n^3)

typedef int type;//实际数据类型,一般是int或double
const type inf = 2e9;
const double eps = 1e-8;
const int maxn = 330;
int n, m;//x中结点个数，y中结点个数，下标从0开始
int matchx[maxn], matchy[maxn];//matchx[i]指的是xi匹配到的y中结点的编号,matchy[j]指的是yj匹配到的x中结点的编号
int visx[maxn], visy[maxn];//访问标记数组
type lx[maxn], ly[maxn];//x,y中每个点的期望值
type w[maxn][maxn];//类似邻接矩阵w[x][y]表示x到y有权值为w[x][y]的边
type slack[maxn];//y中每个元素的slack值
bool dfs(int x) {
visx[x] = 1;
for (int y = 0; y < m; ++y) {
if (visy[y]) continue;
type tmp = lx[x] + ly[y] - w[x][y];
if (tmp == 0) {//double的话改成: if (fabs(tmp)<=eps)
visy[y] = 1;
if (matchy[y] == -1 || dfs(matchy[y])) {
matchx[x] = y;
matchy[y] = x;
return true;
}
}
else {
slack[y] = min(slack[y], tmp);
}
}
return false;
}
void KM() {
memset(matchy, -1, sizeof(matchy));
memset(ly, 0, sizeof(ly));
for (int i = 0; i < n; ++i) {
lx[i] = -inf;
for (int j = 0; j < m; ++j) {
lx[i] = max(lx[i], w[i][j]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) slack[j] = inf;
while (1) {
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(i)) break;
type d = inf;
for (int j = 0; j < m; ++j) {
if (!visy[j]) d = min(d, slack[j]);
}
for (int j = 0; j < n; ++j) { if (visx[j]) lx[j] -= d; }
for (int j = 0; j < m; ++j) {
if (visy[j]) ly[j] += d;
else slack[j] -= d;
}
}
}
}

模板题 hdu2255 http://acm.hdu.edu.cn/showproblem.php?pid=2255

中文题目，裸的二分图最佳完美匹配问题

#include<bits/stdc++.h>
using namespace std;
typedef int type;
const type inf = 2e9;
const double eps = 1e-8;
const int maxn = 330;
int n, m;
int matchx[maxn], matchy[maxn];
int visx[maxn], visy[maxn];
type lx[maxn], ly[maxn];
type w[maxn][maxn];
type slack[maxn];
bool dfs(int x) {
visx[x] = 1;
for (int y = 0; y < m; ++y) {
if (visy[y]) continue;
type tmp = lx[x] + ly[y] - w[x][y];
if (tmp == 0) {
visy[y] = 1;
if (matchy[y] == -1 || dfs(matchy[y])) {
matchx[x] = y;
matchy[y] = x;
return true;
}
}
else {
slack[y] = min(slack[y], tmp);
}
}
return false;
}
void KM() {
memset(matchy, -1, sizeof(matchy));
memset(ly, 0, sizeof(ly));
for (int i = 0; i < n; ++i) {
lx[i] = -inf;
for (int j = 0; j < m; ++j) {
lx[i] = max(lx[i], w[i][j]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) slack[j] = inf;
while (1) {
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(i)) break;
type d = inf;
for (int j = 0; j < m; ++j) {
if (!visy[j]) d = min(d, slack[j]);
}
for (int j = 0; j < n; ++j) { if (visx[j]) lx[j] -= d; }
for (int j = 0; j < m; ++j) {
if (visy[j]) ly[j] += d;
else slack[j] -= d;
}
}
}
}
int main() {
while (scanf("%d", &n) == 1) {
m = n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &w[i][j]);
}
}
KM();
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += w[i][matchx[i]];
}
printf("%dn", ans);
}
return 0;
}