2195(2).cpp

各种算法

// ** Start of PerfectMatch *******************************
// Name: PerfectMatch by Kuhn_Munkras O(n^4)
// Description: w is the adjacency matrix, nx,ny are the size of x and y,
// lx, ly are the lables of x and y, fx[i], fy[i] is used for marking
// whether the i-th node is visited, matx[x] means x match matx[x],
// maty[y] means y match maty[y], actually, matx[x] is useless,
// all the arrays are start at 1
#include <cstdio> 
#include <cstring> 
#include <iostream>
#include <memory.h>
#include <algorithm>
#include <queue> 
#include <math.h> 
using namespace std; 
#include"iostream"
#define INF (int)((unsigned int)(-1)>>1)
#define MAXN 101
int nx,ny,w[MAXN][MAXN];
int lx[MAXN],ly[MAXN];//Xi与Yi的顶标号
int fx[MAXN],fy[MAXN],matx[MAXN],maty[MAXN];
#define M 101
int path(int u)
{
    int v;
    fx[u] = 1;
    for(v = 0;v < ny; v++)
        if((lx[u]+ly[v] == w[u][v])&&(fy[v]<0)) {
            fy[v] = 1;
            if((maty[v]<0)||(path(maty[v]))) {
                matx[u] = v;
                maty[v] = u;
                return(1);
            } // end of if((maty[v]...
        } // end of if((lx[u]...
    return(0);
} // end of int path()

int PerfectMatch()
{
    int ret = 0,i,j,k,p;

    memset(ly,0,sizeof(ly));
    for(i = 0;i < nx; i++) {
        lx[i] = -INF;
        for(j = 0;j < ny; j++)
            if(w[i][j] > lx[i])
                lx[i] = w[i][j];
    } // end of for(i...

    memset(matx,-1,sizeof(matx));
    memset(maty,-1,sizeof(maty));
    for(i = 0;i < nx; i++) {
        memset(fx,-1,sizeof(fx));
        memset(fy,-1,sizeof(fy));
        if(!path(i)) {
            i--;
            p=INF;
            for(k = 0;k < nx; k++)
                if(fx[k] > 0)
                    for(j = 0;j < ny; j++)
                        if( (fy[j]<0) && (lx[k]+ly[j]-w[k][j]<p) )
                            p = lx[k]+ly[j]-w[k][j];
            for(j = 0;j < ny; j++) ly[j] += (fy[j]<0?0:p);
            for(k = 0;k < nx; k++) lx[k] -= (fx[k]<0?0:p);
        } // end of if(!path(i))
    } // end of for(i...

    for(i = 0;i < ny; i++) ret += w[maty[i]][i];
    return ret;
} // end of int PerfectMatch()
// ** End of PerfectMatch *********************************
struct part
{
	int i;
	int j;
}man[M],house[M]; 
int main() 
{ 
   int n, m; //  w[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++){
				w[i][j] = -abs(man[i].i - house[j].i)-abs(man[i].j - house[j].j);
			}
		}
		nx = size0;ny = size1;
		int cost = PerfectMatch();
		printf("%d\n",-cost);
	}
   // cost 为最大匹配的总和, match[]中保存匹配信息   
   return 0; 
}