2849838_ac_15ms_180k.cpp

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

#include <stdio.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;
			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(!vy[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&&m)
	{
		l = h = 0;
		char c;
		getchar();
           for ( i = 1; i <= n; i++ ){
                 for ( j = 1; j <= m; j++ ){
                       scanf("%c", &c);
                       if ( c == 'H' ){
                            home[ h ][0] = i;
                            home[ h ][1] = j;
                            h ++;
                       }else if ( c == 'm' ){
                            man[ l ][0] = i;
                            man[ l ][1] = j;
                            l ++;      
                       }
                 }
                 getchar();
           }

		for(i = 0; i < l; i++)
			for(j = 0; j < l; j++)
			{
				int cc, dd;
				cc = man[i][0]-home[j][0];
				if(cc<0)
					cc *= -1;
				dd = man[i][1]-home[j][1];
				if(dd<0)
					dd *= -1;
				edge[i][j] = cc+dd;
			}
		KM();
		cost = 0;
		for (i = 0; i < l; i++)
			cost += edge[link[i]][i];
		printf("%d\n", cost );
	}
	return 1;
}