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

题意：

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

分析：

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

代码：

//poj 2195
//sep9
#include 
  
   
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
   
    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
    
     lx[i]) lx[i]=w[i][j]; for(int x=0;x
     
      -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