(模板)KM算法——带权二分图的最大匹配

升级版匈牙利算法

题意概述

有n个人，n个房子，每个人到房子都有一定的距离，问怎么匹配总距离最小

思路

1. 可以看成是一个二分图，人在左集合，房子在右集合
2. 这就是一个带权二分图的最优匹配问题
3. 但是让求的是最小匹配怎么办呢，可以把权值存成负数，输出的时候再加一个负号就好了

算法主要步骤

1. 为左右集合设置顶标，左集合顶标为所连线权值最大值，左集合顶标为0, 设
2. 如果 ,则
3. 为左集合匹配，匹配成功更好，匹配失败的话，遍历左集合已经匹配的点，让他们降低标准，让代价最小，为。然后遍历右集合未匹配的点，符合要求就做匹配
4. 再次匹配后，遍历本轮匹配过程中遍历过的点，左集合减去, 右集合加上

代码

#include <bits/stdc++.h>
inline int read()
{
    int x = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            flag = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * flag;
}
const int maxn = 0x7f7f7f7f;
const int minn = 0xf7;
int people = 0, house = 0;
int N = 1, M = 1;
int peo[104][2], home[104][2]; // 存一下房子和人的坐标
int val[104][104]; // 存边权
int lx[104], ly[104]; // 左顶标和右顶标
int Link[104]; // 每一个房子匹配的人是哪一个
bool visx[104]; // 是否已经访问过左集合的点
bool visy[104]; // 是否已经访问过右集合的点 

bool dfs(int x) // 找匹配
{
    visx[x] = 1;
    for (int i = 1; i <= house; i++)
    {
        if (visy[i] == 0 && lx[x] + ly[i] == val[x][i])
        {
            visy[i] = 1;
            if (Link[i] == -1 || dfs(Link[i]))
            {
                Link[i] = x;
                return true;
            }
        }
    }
    return false;
}

void solve()
{
    // 存边权
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            char tmp;
            scanf(" %c", &tmp);
            if (tmp == 'm') // 如果这是个人的话
            {
                peo[++people][0] = i;
                peo[people][1] = j;
            }
            else if (tmp == 'H')
            {
                home[++house][0] = i;
                home[house][1] = j;
            }
            
        }
    }
    for (int i = 1; i <= people; i++)
    {
        for (int j = 1; j <= house; j++)
        {
            val[i][j] = -(abs(peo[i][0] - home[j][0]) + abs(peo[i][1] - home[j][1]));
        }
    }
    // 把左集合顶标赋值成两边权值的最大值
    for (int i = 1; i <= people; i++)
    {
        for (int j = 1; j <= house; j++)
        {
            lx[i] = std::max(lx[i], val[i][j]);
        }
    }
    // 右集合顶标已经是0了就不用赋值了

    // 开始为每一个人去匹配
    for (int i = 1; i <= people; i++)
    {
        while(true) // 一直匹配，直到成功为止
        {
            // 注意是在“这一轮匹配中”
            memset(visx, 0, sizeof(visx));
            memset(visy, 0, sizeof(visy));
            if (dfs(i)) break; // 如果匹配成功就退出循环
            // 如果匹配不成功
            int delta = maxn;
            for (int j = 1; j <= people; j++)
            {
                // 找左集合访问过的点，降低标准，代价尽可能小，再次匹配
                if (visx[j])
                {
                    for (int k = 1; k <= house; k++)
                    {
                        if (visy[k] == 0) // 找右边还没有匹配的匹配
                        {
                            delta = std::min(delta, lx[j] + ly[k] - val[j][k]);
                        }
                    }
                }
            }
            if (delta == maxn) return; // 匹配失败，防止死循环（本题中不可能出现这种情况）
            for (int j = 1; j <= people; j++)
            {
                if (visx[j]) lx[j] -= delta;
            }
            for (int j = 1; j <= house; j++)
            {
                if (visy[j]) ly[j] += delta;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= house; i++)
    {
        ans += val[Link[i]][i];
    }
    std::cout << -ans << '\n';
}

int main()
{
    //freopen("out.txt", "w", stdout);
    
    while(N != 0 && M != 0)
    {
        N = read();
        M = read();
        if (N == 0 && M == 0) break;
        people = 0, house = 0;
        memset(lx, minn, sizeof(lx));
        memset(ly, 0, sizeof(ly));
        memset(Link, -1, sizeof(Link));
        //N = read(), M = read();
        solve();
    }
    return 0;
}