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;
} 
时间: 12-05

poj 2195 Going Home 二分图最小权匹配KM算法的相关文章

[ACM] HDU 1533 Going Home (二分图最小权匹配,KM算法)

Going Home Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2963    Accepted Submission(s): 1492 Problem Description On a grid map there are n little men and n houses. In each unit time, every

POJ 1325 Machine Schedule (二分图最小点集覆盖 匈牙利算法)

Machine Schedule Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 12621   Accepted: 5399 Description As we all know, machine scheduling is a very classical problem in computer science and has been studied for a very long history. Scheduli

HDU 1533 二分图最小权匹配 Going Home

带权二分图匹配,把距离当做权值,因为是最小匹配,所以把距离的相反数当做权值求最大匹配. 最后再把答案取一下反即可. 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <map> 6 #include <vector> 7 #include <cmath> 8 #define MP

POJ 3686 The Windy&#39;s【最小权匹配(神建图啊)】

大意:有n个任务m个机器,告诉你n*m的矩阵表示每个任务在每个机器上完成需要的时间 问所有任务完成的总时间最少?(比如第一个任务在第一分钟完成第二个任务在第二分钟完成   则总时间为1 + 2 = 3 分析: 该题自己做的时候没有思路 后来在网上搜题解,感觉建图真是太厉害了 假设最优情况下,个个任务需要的时间分别为a1, a2, a3, ……,an 那么总时间t = n * a1 + (n - 1) * a2 + ……+ 2 * an - 1 + an 也就是说只需要考虑系数就可以了 我们先假设

POJ 3686 The Windy&#39;s 最小权值匹配

点击打开链接 The Windy's Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 3788   Accepted: 1630 Description The Windy's is a world famous toy factory that owns M top-class workshop to make toys. This year the manager receives N orders for toys.

poj3565Ants【最小权匹配】

大意: 左图为一个坐标轴上的点  其中黑点代表ants 白点代表apple 问怎样安排ants匹配apple才能使人一两条边不想交 分析: 如左图,我们假设a->d,b->c为一个最佳匹配  交点为e 那么ad+bc = ae+ ed + be + ec = (ae + ec) + (be + ed)  该值大于ac+bd 所以匹配为最佳匹配不成立 因此我们只要求出二分图的最小匹配就是结果了 但是wa了: wa的代码: 1 #include <iostream> 2 #includ

poj 2226 Muddy Fields(二分图最小点覆盖)

B - Muddy Fields Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submit Status Practice POJ 2226 Description Rain has pummeled the cows' field, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <

ural 1076 KM求最小权匹配

贴模板~ KM算法引进了顶标函数,不断缩小这个顶标来让相等子图的可能范围扩大 #include<iostream> #include<cstring> //KM 复杂度O^3 using namespace std; const int N=200; int lx[N],ly[N];//顶标函数 int w[N][N];//图 bool vix[N],viy[N]; int linky[N];// int lack;//每次顶标函数扩大的增量 int n,m; bool find(

LA4043 - Ants(二分图完备最佳匹配KM)

option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044">https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2044 大致题意: 平面上有n个白点和n个黑点,求一种完美匹配使他们间的连线不相交 思路:要注意到,若有两种匹