题解 | #Going Home#

Going Home

题目描述：

给你一张n * m的地图，里面有若干个小人，用'm'表示，同样的，有相同数量的房子，用'H'表示，每个人可以进入任意一个房子，不过每个房子只能住一个人，现在你需要计算所有人住满房子最少需要走多少步

思路：

因为房子数量=人的数量，所以是在二分图的完美匹配的基础上求最小权值和

之前求的都是最大权值和，这里求最小，只需要在建图的时候处理成负权边即可

我们只需要按照左集合是人，右集合是房子，来连边即可，连边之前需要预处理出来哪些点需要连，权值是多少

我这里用两个内嵌结构体点vector来分别存人和房子

每个人对每个房子去求权值，也就是两个点横坐标与纵坐标的和的差的绝对值的相反数(即 $-|x1 + y1 - x2 - y2|$

预处理完了以后就套KM的板子即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX  100 + 50
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;
//不开longlong见祖宗!提交不看数据范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, num;
char x;
int tr[MAX][MAX];//最终的图的权值
struct ran{//记录点的横纵坐标
    int x, y;
};

//KM板子
int lx[MAX], ly[MAX], link[MAX];
bool visx[MAX], visy[MAX];

bool dfs(int x){
    visx[x] = 1;
    for(int i = 1; i <= num; ++i){
        if(!visy[i] && lx[x] + ly[i] == tr[x][i]){
            visy[i] = 1;
            if(link[i] == -1 || dfs(link[i])){
                link[i] = x;
                return true;
            }
        }
    }
    return false;
}

int KM(){
    mem(ly, 0);
    mem(lx, 0xf7);
    mem(link, -1);
    for(int i = 1; i <= num; ++i){
        for(int j = 1; j <= num; ++j){
            lx[i] = max(lx[i], tr[i][j]);
        }
    }
    for(int i = 1; i <= num; ++i){
        while (1) {
            mem(visy, 0);
            mem(visx, 0);
            if(dfs(i))break;
            int d = inf;
            for(int j = 1; j <= num; ++j){
                if(visx[j]){
                    for(int k = 1; k <= num; ++k){
                        if(!visy[k]){
                            d = min(d, lx[j] + ly[k] - tr[j][k]);
                        }
                    }
                }
            }
            if(d == inf)return -1;
            for(int j = 1; j <= num; ++j){
                if(visx[j])lx[j] -= d;
            }
            for(int j = 1; j <= num; ++j){
                if(visy[j])ly[j] += d;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= num; ++i){
        ans += tr[link[i]][i];
    }
    ans = 0 - ans;
    return ans;
}

int main(){
    while (sdd(n, m) && n + m) {//多组输入
        num = 0;//记录人的数量
        vector<ran>vh;//房子的坐标
        vector<ran>vm;//人的坐标
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                cin>>x;
                if(x == 'H'){
                    ++num;
                    vh.push_back({i,j});
                }
                else if(x == 'm'){
                    vm.push_back({i, j});
                }
            }
        }
        for(int i = 0; i < vh.size(); ++i){//建图
            for(int j = 0; j < vm.size(); ++j){
                tr[i + 1][j + 1] = 0 - (abs(vh[i].x - vm[j].x) + abs(vh[i].y - vm[j].y));
            }
        }
        cout<<KM()<<endl;
    }

    return 0;
}

/*
 7 8
 ...H....
 ...H....
 ...H....
 mmmHmmmm
 ...H....
 ...H....
 ...H....
 */