# poj 2195 Going Home 二分图最小权匹配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;
} ```

## [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

## 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 <

## 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个黑点,求一种完美匹配使他们间的连线不相交 思路:要注意到,若有两种匹