3020_antenna placement_hungary.cpp

各种算法

#include"memory.h"
#include"stdio.h"
#define L_MAX 201
#define R_MAX 201
bool ckd[R_MAX];
int link[R_MAX];
int l_num,r_num;
bool array[L_MAX][R_MAX];
int table[41][11];
bool augment_path(int t)//找交错路径
{
	for(int i = 0;i < r_num; i++)
	{	if(!ckd[i] && array[t][i]){
			ckd[i] = true;
			if(link[i] == -1 || augment_path(link[i])){
				link[i] = t;
				return true;
			}
		}
	}
	return false;
}
int hungary()//匈牙利算法
{	
	memset(link,-1,sizeof link);
	int num = 0;
	for(int i = 0;i < l_num;i++){
		memset(ckd,0,sizeof ckd);
		if(augment_path(i)) num++;
	}
	return num;
}
void mapping(int i,int j)
{
	int k = (i+j)%2;
	if(k)
		table[i][j] = l_num++;
	else 
		table[i][j] = r_num++;
	int p;int q = table[i][j];
	if(i-1 > -1 && table[i-1][j] > -1)	//细节处
	{	p = table[i-1][j];
		array[ p*(1-k)+q*k ][ p*k+q*(1-k) ] = true;
	}
	if(j-1 > -1 && table[i][j-1] > -1)
	{	p = table[i][j-1];
		array[ p*(1-k)+q*k ][ p*k+q*(1-k) ] = true;
	}
}
int main()
{
	int n;int i,j;
	scanf("%d",&n);
	while(n--)
	{
		char c;
		int  h,w;l_num = r_num = 0;int sum = 0;
		memset(table,-1,sizeof table);
		memset(array,0,sizeof array);
		scanf("%d%d",&h,&w);
		for(i = 0;i < h;i++)
		{	scanf("\n");
			for(j = 0;j < w;j++){
				scanf("%c",&c);	
				if(c == '*'){
					mapping(i,j);
				}
			}
		}
		sum = hungary();
		printf("%d\n",l_num+r_num-sum);
	}
	return 1;
}