poj 2195 Going Home 二分圖最小權匹配KM算法

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;yt)
			slack[y]=t;
	}	
	return false;
}

int KM()
{
	int i,j;
	memset(linky,-1,sizeof(linky));
	memset(ly,0,sizeof(ly));
	for(i=0;ilx[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