【POJ 2195】 Going Home(KM算法求最小权匹配)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【POJ 2195】 Going Home(KM算法求最小权匹配),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4170字,纯文字阅读大概需要6分钟。
内容图文
![【POJ 2195】 Going Home(KM算法求最小权匹配)](/upload/InfoBanner/zyjiaocheng/1069/009dd33dbd5f487a9f1c33447df4730a.jpg)
【POJ 2195】 Going Home(KM算法求最小权匹配)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 20303 | Accepted: 10297 |
Description
Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a ‘.‘ means an empty space, an ‘H‘ represents a house on that point, and am ‘m‘ indicates there is a little man on that point.
![技术分享](/upload/getfiles/default/2022/11/5/20221105064915356.jpg)
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
Input
Output
Sample Input
2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0
Sample Output
2 10 28
Source
越来越认为KM算法是种非常奇妙的算法,或者说各种图论算法都好奇妙……在或者说 图是一种奇妙的东西。。。一个题可能有多种算法能够解决
这题之前一仅仅用最小费做的,一直以为是唯一的做法。
今天做KM突然发现 这题之前不是做过么……
这题用KM算法会快非常多。并且代码量少一点。
只是思想的算法。没法做什么比較。
题目大意就是一定数量的人和房子。保证人和房子数量同样,要求分配每一个人到相应的房子里,而且人与房子一一相应。问全部人须要移动的最少步数。建图我是把人和房子的坐标用pair存成数组,然后求出每一个人到每一个房子的距离。也就是最初的二分图。
之后用KM求最小权,跟最大权一种套路,仅仅只是建图的时候权值取负,这样求出的最大权事实上绝对值是最小的。换句话说取反回来后,事实上就是所求的解。
代码例如以下:
#include <iostream> #include <cmath> #include <vector> #include <cstdlib> #include <cstdio> #include <cstring> #include <queue> #include <list> #include <algorithm> #include <map> #include <set> #define LL long long #define fread() freopen("in.in","r",stdin) #define fwrite() freopen("out.out","w",stdout) #define Pr pair<int,int> using namespace std; const int INF = 0x3f3f3f3f; const int msz = 10000; const double eps = 1e-8; //二分图 int mp[233][233]; // x顶标 y顶标 int lx[233],ly[233],link[233],slick[233]; bool visx[233],visy[233]; // 人的坐标 房子坐标 Pr human[233],house[233]; //人数 房数 int nm,nh; bool cal(int x) { visx[x] = 1; for(int y = 0; y < nh; ++y) { if(visy[y]) continue; int t = lx[x]+ly[y]-mp[x][y]; if(t == 0) { visy[y] = 1; if(link[y] == -1 || cal(link[y])) { link[y] = x; return true; } } else slick[y] = min(slick[y],t); } return false; } int KM() { memset(link,-1,sizeof(link)); for(int i = 0; i < nm; ++i) { memset(slick,INF,sizeof(slick)); while(1) { memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(cal(i)) break; int d = INF; for(int j = 0; j < nh; ++j) if(!visy[j]) d = min(d,slick[j]); for(int j = 0; j < nm; ++j) if(visx[j]) lx[j] -= d; for(int j = 0; j < nh; ++j) if(visy[j]) ly[j] += d; else slick[j] -= d; } } int ans = 0; for(int i = 0; i < nh; ++i) if(link[i] != -1) ans += mp[link[i]][i]; return ans; } int main() { int n,m; char tmp[233]; while(~scanf("%d%d",&n,&m) && (n+m)) { nm = nh = 0; for(int i = 0; i < n; ++i) { scanf("%s",tmp); for(int j = 0; j < m; ++j) if(tmp[j] == 'm') human[nm++] = Pr(i,j); else if(tmp[j] == 'H') house[nh++] = Pr(i,j); } memset(lx,0,sizeof(lx)); memset(ly,0,sizeof(ly)); for(int i = 0; i < nm; ++i) for(int j = 0; j < nh; ++j) { mp[i][j] = -(abs(human[i].first-house[j].first)+abs(human[i].second-house[j].second)); lx[i] = max(lx[i],mp[i][j]); } printf("%d\n",-KM()); } return 0; }
原文:http://www.cnblogs.com/liguangsunls/p/7131937.html
内容总结
以上是互联网集市为您收集整理的【POJ 2195】 Going Home(KM算法求最小权匹配)全部内容,希望文章能够帮你解决【POJ 2195】 Going Home(KM算法求最小权匹配)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。