1654_robots.cpp

各种算法

// zju 1654 二部图

#include"memory.h"
#include"stdio.h"
#define L_MAX 1303
#define R_MAX 1303
bool ckd[R_MAX];
int link[R_MAX];
int l_num,r_num;
bool array[L_MAX][R_MAX];
struct table
{	int l,r;
}table[51][51];
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,char c)
{	int k;
	if(c == '#')
	{table[i][j].l = table[i][j].r = -2;}
	if(c == '*')
	{table[i][j].l = table[i][j].r = -1;}
	if(c == 'o') {
		for(k = i-1;k >= 0;k--) {
			if(table[k][j].r >= 0)	{table[i][j].r = table[k][j].r;break;}
			if(table[k][j].r == -2||k == 0) {table[i][j].r = r_num++;break;}
		}
		for(k = j-1;k >= 0;k--) {
			if(table[i][k].l >= 0)	{table[i][j].l = table[i][k].l;break;}
			if(table[i][k].l == -2||k == 0) {table[i][j].l = l_num++;break;}
		}
		array[ table[i][j].l ][ table[i][j].r ] = 1;
	}
}
int main()
{
	int n;int i,j,k;int h,w;char c;
	scanf("%d",&n);
	for(k = 1;k <= n; k++)
	{	int sum = 0;
		l_num = r_num = 51;
		memset(table,0,sizeof table);
		for(i = 0;i < 51;i++)	
			{ table[i][0].l = table[0][i].r = i;}
		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);	
				mapping(i,j,c);
			}
		}
		sum = hungary();
		printf("Case :%d\n%d\n",k,sum);
	}
	return 1;
}