2520124_tle.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <string.h>
#define INF 100000000

int n, m;
char map[101][101];
int l, h;
int man[101][2], home[101][2];
int edge[101][101];
int Map[101][101], link[101];
int vx[101], vy[101];

int dfs(int v)
{
	int i, t;

	for(i = 0; i < l; i++)
	{
		if(Map[v][i]&&!vy[i])
		{
			vy[i] = 1;
			t = link[i];
			link[i] = v;
			if(t==-1||dfs(t))
				return 1;
			link[i] = t;
			if(t!=-1)
				vx[t] = 1;
		}
	}
	return 0;
}

void KM()
{
	int i, j, live, min, t;
	int lx[100], ly[100];
	int perfect;

	for(i = 0; i < l; i++)
	{
		lx[i] = 0;
		ly[i] = INF;
		for(j = 0; j < l; j++)
			if(edge[j][i]<ly[i])
				ly[i] = edge[j][i];
	}
	
	perfect = 0;
	while(!perfect)
	{
		for(i = 0; i < l; i++)
		{
			for(j = 0; j < l; j++)
			{
				if(lx[i]+ly[j]==edge[i][j])
					Map[i][j] = 1;
				else
					Map[i][j] = 0;
			}
		}
		live = 0;
		memset(link,-1,sizeof(link));
		for(i = 0; i < l; i++)
		{
			memset(vx,0,sizeof(vx));
			memset(vy,0,sizeof(vy));
			if(dfs(i))
				live++;
			else
			{
				vx[i] = 1;
				break;
			}
		}
		if(live==l)
			perfect = 1;
		else
		{
			min = INF;
			for(i = 0; i < l; i++)
				for(j = 0; vx[i]&&j < l; j++)
					if((t = -(lx[i]+ly[j]-edge[i][j]))<min)
						min = t;
			for(i = 0; i < l; i++)
			{
				if(vx[i])
					lx[i] += min;
				if(vy[i])
					ly[i] -= min;
			}
		}
	}
}

int main()
{
	int i, j;
	int cost;

	while(scanf("%d%d",&n,&m)==2,n)
	{
		l = h = 0;
		for(i = 0; i < n; i++)
			scanf("%s",map[i]);
		for(i = 0; i < n; i++)
			for(j = 0; j < m; j++)
			{
				if(map[i][j]=='m')
				{
					man[l][0] = i;
					man[l][1] = j;
					l++;
				}
				if(map[i][j]=='H')
				{
					home[h][0] = i;
					home[h][1] = j;
					h++;
				}
			}
		for(i = 0; i < l; i++)
			for(j = 0; j < h; j++)
				edge[i][j] = abs(man[i][0]-home[j][0])+abs(man[i][1]-home[j][1]);
		KM();
		cost = 0;
		for (i = 0; i < l; i++)
			cost += edge[link[i]][i];
		printf("%d\n", cost );
	}
	return 1;
}