专注收集记录技术开发学习笔记、技术难点、解决方案
网站信息搜索 >> 请输入关键词:
您当前的位置: 首页 > Go

poj 2195 Going Home 二分图最小权婚配KM算法

发布时间:2011-06-29 18:28:20 文章来源:www.iduyao.cn 采编人员:星星草
poj 2195 Going Home 二分图最小权匹配KM算法

题意:

有n个人要回到n间房子里,每间房子只允许一个人,求n个人要走的最小距离和。

分析:

裸的二分图最小权匹配,KM搞之。

代码:

//poj 2195
//sep9
#include <iostream>
using namespace std;
const int maxN=128;
char g[maxN][maxN];
int mx[maxN],my[maxN],hx[maxN],hy[maxN];
int w[maxN][maxN];
int lx[maxN],ly[maxN],linky[maxN];
int visx[maxN],visy[maxN];
int slack[maxN];
int nx,ny;

bool find(int x)
{
	visx[x]=true;
	for(int y=0;y<ny;++y){
		if(visy[y])
			continue;
		int t=lx[x]+ly[y]-w[x][y];
		if(t==0){
			visy[y]=true;
			if(linky[y]==-1||find(linky[y])){
				linky[y]=x;
				return true;
			}
		}
		else if(slack[y]>t)
			slack[y]=t;
	}	
	return false;
}

int KM()
{
	int i,j;
	memset(linky,-1,sizeof(linky));
	memset(ly,0,sizeof(ly));
	for(i=0;i<nx;++i)
		for(j=0,lx[i]=INT_MIN;j<ny;++j)
			if(w[i][j]>lx[i])
				lx[i]=w[i][j];
	for(int x=0;x<nx;++x){
		for(i=0;i<ny;++i)
			slack[i]=INT_MAX;
		while(1){
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			if(find(x))
				break;
			int d=INT_MAX;
			for(i=0;i<ny;++i)
				if(!visy[i]&&slack[i]<d)
					d=slack[i]; 
			if(d==INT_MAX)
				return -1;
			for(i=0;i<nx;++i)
				if(visx[i])
					lx[i]-=d;
			for(i=0;i<ny;++i)
				if(visy[i])
					ly[i]+=d;
				else
					slack[i]-=d;
		}
	}
	int result=0;
	for(i=0;i<ny;++i)
		if(linky[i]>-1)
			result+=w[linky[i]][i];
	return result;				
}

int main()
{
	int i,j,n,m;
	while(scanf("%d%d",&n,&m)==2){
		if(n==0&&m==0)
			break;
		for(i=0;i<n;++i)
			scanf("%s",g[i]);
		int mcnt=0,hcnt=0;
		for(i=0;i<n;++i)
			for(j=0;j<m;++j)
				if(g[i][j]=='m'){
					mx[mcnt]=i;
					my[mcnt]=j;
					++mcnt;
				}
				else if(g[i][j]=='H'){
					hx[hcnt]=i;
					hy[hcnt]=j;
					++hcnt;
				}	
		for(i=0;i<mcnt;++i)
			for(j=0;j<hcnt;++j){
				w[i][j]=abs(mx[i]-hx[j])+abs(my[i]-hy[j]);
				w[i][j]=-w[i][j];
			}
		nx=ny=mcnt;
		printf("%d\n",-KM());
	}
	return 0;	
} 


友情提示:
信息收集于互联网,如果您发现错误或造成侵权,请及时通知本站更正或删除,具体联系方式见页面底部联系我们,谢谢。

其他相似内容:

  • ModernUI课程:定义一个Logo

    ModernUI教程:定义一个Logo ModernWindow的标题栏包含了一块区域用来显示自定义的窗体Logo: 这个窗体logo通过ModernWindow.LogoD...

  • Django忘记管理员账号和密码的解决方法

    Django忘记管理员账号和密码的解决办法 看着Django的教程学习搭建网站,结果忘记第一次创建的账号和密码了。结果搭建成功以后,一直...

  • GO语言小结(1)——基本知识

    GO语言总结(1)——基本知识 1、注释(与C++一样)   行注释://  块注释:/*   ...  */ 2、标识符   可以这么说,除了数字开头...

  • golang 惯用的文件读取方式

    golang 常用的文件读取方式 Golang 的文件读取方法很多,刚上手时不知道怎么选择,所以贴在此处便后速查。 一次性读取 小文件推荐一...

  • 查询深圳市通相关信息

    查询深圳通相关信息 用 HTTP.GET 从开放 API 中查询深圳通信息,然后将 JSON 数据存入结构体中,再格式化输出。 注意:获取的并不是实...

  • Go语言设计模式实践:结合(Composite)

    Go语言设计模式实践:组合(Composite) 关于本系列 这个系列首先是关于Go语言实践的。在项目中实际使用Go语言也有段时间了,一个体会就...

  • 列出索引和遍历目录

    列出目录和遍历目录 获取目录列表用 ioutil.ReadDir(),遍历目录用 filepath.Walk(),使用方法请参考文章示例。 示例代码: package ma...

  • io 包的惯用接口速记

    io 包的常用接口速记 我没有 C/C++ 基础,没有接口的概念,且从 Python 投奔而来,Python 的极简主义(一个结果往往只提供一个方法),让我在...

  • 代理服务扩充

    代理服务扩展 之前自己实现了一个代理服务,当时考虑的是只要支持SOCKS5就好了,因为我经常用CHROME,配合着SwitchySharp,体验还是很棒...

  • 文件的创造与打开

    文件的创建与打开 文件操作是个很重要的话题,使用也非常频繁,熟悉如何操作文件是必不可少的。Golang 对文件的支持是在 os package ...

热门推荐: