2195_goning home.cpp

各种算法

#include <cstdio> 
#include <cstring> 
#include <iostream>
#include <memory.h>
#include <algorithm>
#include <math.h> 
using namespace std; 
#include"iostream"
#define INF (int)((unsigned int)(-1)>>1)
#define M 101
const int size = 101; 

bool map[size][size];         // 二分图的相等子图, map[i][j] = true 代表Xi与Yj有边 
bool xckd[size], yckd[size];  // 标记在一次DFS中，Xi与Yi是否在交错树上 
int match[size];              // 保存匹配信息，其中i为Y中的顶点标号，match[i]为X中顶点标号 

int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
bool DFS(int, const int); 
bool KM_Perfect_Match(const int n, const int edge[][size])
{ 
	int i, j; 
	int lx[size], ly[size];   //  KM算法中Xi与Yi的顶标号 
	for(i = 0; i < n; i++) { 
		lx[i] = -INF; 
		ly[i] = 0; 
		for(j = 0; j < n; j++) { 
			lx[i] = max(lx[i], edge[i][j]); 
		} 
	} 
    bool perfect = false; 
    while(!perfect) {
      //  初始化等式子图 
        for(i = 0; i < n; i++) { 
            for(j = 0; j < n; j++) { 
            if(lx[i]+ly[j] == edge[i][j]) 
				map[i][j] = true; 
            else map[i][j] = false; 
			} 
		} 
      // 匹配过程 
		int live = 0; 
		memset(match, -1, sizeof(match)); 
		for(i = 0; i < n; i++) { 
			memset(xckd, false, sizeof(xckd)); 
			memset(yckd, false, sizeof(yckd)); 
			if(DFS(i, n)) live++; 
			else { 
				xckd[i] = true; 
				break; 
			} 
		} 
		if(live == n) perfect = true; 
		else { 
         // 修改标号过程 
			int ex = INF; 
			for(i = 0; i < n; i++) { 
				for(j = 0; xckd[i] && j < n; j++) { //xckd[i] == 1放在上层就错了
					if(!yckd[j]) ex = min(ex, lx[i]+ly[j]-edge[i][j]); 
				} 
			} 
			for(i = 0; i < n; i++) { 
				if(xckd[i]) lx[i] -= ex; 
				if(yckd[i]) ly[i] += ex; 
			} 
		} 
	} 
	return perfect;
} 

// 此函数用来寻找是否有以Xp为起点的增广路径，返回值为是否含有增广路 

bool DFS(int p, const int n) //hangary算法
{ 
   int i; 
   for(i = 0; i < n; i++) { 
      if(!yckd[i] && map[p][i]) { 
         yckd[i] = true; 
         int t = match[i]; 
         match[i] = p;				//有冗余
         if(t == -1 || DFS(t, n)) { 
            return true; 
         } 
         match[i] = t; 
         if(t != -1) xckd[t] = true; 
      } 
   } 
   return false; 
} 
struct part
{
	int i;
	int j;
}man[M],house[M]; 
int main() 
{ 
   int n, m,edge[size][size]; //  edge[i][j]为连接Xi与Yj的边的权值 
   int i,j;int size0,size1;char c;
	while(scanf("%d%d",&n,&m),n != 0&&m != 0)
	{	size0 = 0;size1 = 0;
		for(i = 0;i < n; i++)
		{	scanf("\n");
			for(j = 0;j < m; j++){
				scanf("%c",&c);
				if(c == 'm') {  man[size0].i = i;  man[size0++].j = j;}
				if(c == 'H') {house[size1].i = i;house[size1++].j = j;}
			}
		}
		for(i = 0;i < size0;i++){
			for(j = 0;j < size1;j++){
				edge[i][j] = -abs(man[i].i - house[j].i)-abs(man[i].j - house[j].j);
			}
		}
		n = size0;
		KM_Perfect_Match(n, edge);
		int cost = 0;
		for(i = 0; i < n; i++) cost += edge[match[i]][i];
		printf("%d\n",-cost);
	}
   // cost 为最大匹配的总和, match[]中保存匹配信息   
   return 0; 
}