题意：这里有一个N*M的方格图.....图中m代表人，H代表房子...并且人数和房子的数量是相等的..那么.每个人可以竖直或者横向走一格，并且花费1S元...那么为了让所有的人进入房子，求解最小的花费

分析...：这里很明显 ，就是用人去和房子匹配，并且匹配的权值就是花费.就是求解完备最小权值匹配..那么在输入的时候我们记录每一个人和房子的坐标...那么求解所有的人到所有的房子的距离(即是花费)，我们取负值然后用KM算法匹配即可得到答案;;

上马：

 

// 15MS 272K #include
    
     #include
     
      #include
      
       #define MAX 101#define INF 1<<30-1;int N,M;int man[MAX][2],tol_m;//记录人的坐标和人数int house[MAX][2],tol_h;//记录房子坐标和房子数int map[MAX][MAX];//map[i][j]表示第i个人到第j个房子的距离（花费）int link[MAX],lx[MAX],ly[MAX],slar[MAX];bool visx[MAX],visy[MAX];bool dfs(int x){	visx[x]=true;	for(int y = 0; y < tol_h; y ++)	{		if(visy[y]) continue;		int t = lx[x] + ly[y] -map[x][y];		if(t == 0)		{			visy[y]=true;			if(link[y] == -1 || dfs(link[y]))			{				link[y]=x;return true;			}		}		else			slar[y]=slar[y]>t ? t:slar[y];	}	return false;}int KM(){	int i,j;	memset(ly,0,sizeof(ly));	memset(link,-1,sizeof(link));	for( i = 0 ; i < tol_m ; i++)	{		lx[i]=-INF;		for( j = 0 ; j < tol_h ; j++)			lx[i]=lx[i]>map[i][j] ? lx[i]:map[i][j];	}	for(int x = 0; x < tol_m ; x ++ )	{		for(i = 0;i 
       
        slar[i] ? slar[i]:d;			for(i = 0;i < tol_m; i ++)				if(visx[i]) lx[i] -= d;			for(i = 0; i< tol_h ; i ++)				if(visy[i]) ly[i] +=  d;				else  slar[i] -=d;		}	}	int ans=0;	for(i = 0;i < tol_h;i ++)		if(link[i] != -1) ans+=map[link[i]][i];	return ans;}int main(){	int i,j;	char ch[MAX];	while(scanf("%d%d",&N,&M),N+M)	{		tol_m=tol_h=0;		for(i=0;i
       
      
     
    

个人愚昧观点，欢迎指正和讨论