题解 | #Going Home#

Going Home

题目描述:

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

思路:

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

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

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

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

每个人对每个房子去求权值,也就是两个点横坐标与纵坐标的和的差的绝对值的相反数(即

预处理完了以后就套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....
 */
全部评论

相关推荐

昨天 11:26
清华大学 Java
打开电脑,思绪又回到了7月份刚开始的时候,感觉这个月过的如梦如幻,发生了太多事,也算是丰富了我本就是平淡的人生吧太早独立的我习惯了一切都是自己做决定,拥有绝对的决定权,而且永远不会听取别人的建议。我就是那个恋爱四年出轨的男主啦,感觉既然在牛客开了这个头,那我就要做个有始有终的人。从我出轨到结束再到和女朋友和好如初真的太像一场梦了,短短的一个月我经历了太多,也成长了很多,放下了那些本就不属于我的,找回了那些我不该放弃的。我的人生丰富且多彩,但人不能一直顺,上天总会让你的生活中出点乱子,有好有坏,让你学会一些东西,让你有成长。我和女朋友的恋爱四年太过于平淡,日常除了会制造一些小浪漫之外,我们的生活...
段哥亡命职场:不得不说,我是理解你的,你能发出来足见你是个坦诚的人,至少敢于直面自己的内心和过往的过错。 这个世界没有想象中那样非黑即白,无论是农村还是城市,在看不见的阴影里,多的是这样的事。 更多的人选择站在制高点去谩骂,一方面是社会的道德是需要制高点的,另一方面,很多人不经他人苦,却劝他人善。 大部分的我们,连自己生命的意义尚且不能明晰,道德、法律、困境,众多因果交织,人会迷失在其中,只有真的走出来之后才能看明白,可是没走出来的时候呢?谁又能保证自己能走的好,走的对呢? 可是这种问题有些人是遇不到的,不去追寻,不去探寻,也就没了这些烦恼,我总说人生的意义在过程里,没了目标也就没了过程。 限于篇幅,没法完全言明,总之,这世界是个巨大的草台班子,没什么过不去了,勇敢面对,革故鼎新才是正确,祝你早日走出来。查看图片
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务