有没有大佬帮帮萌新(KM)
  • 板块学术版
  • 楼主A524
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/2/22 19:28
  • 上次更新2023/11/5 02:52:22
查看原帖
有没有大佬帮帮萌新(KM)
484922
A524楼主2021/2/22 19:28
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int i,j,t,w,n,m,lef[110],lx[110],ly[110],f[110][110];bool S[110],T[110];
char a[110][110];struct node{int x,y;}b[110],c[110];
bool match(int i){
	S[i]=1;int j;
	for (j=1;j<=t;j++)
		if (lx[i]+ly[j]==f[i][j]&&!T[j]){
			T[j]=1;
			if (!lef[j]||match(lef[j]))
				{lef[j]=i;return 1;}
		}
	return 0;
}
void update(){
	int a=(1<<30),i,j;
	for (i=1;i<=t;i++)
		if (S[i])
			for (j=1;j<=t;j++)
				if (!T[i]) a=min(a,lx[i]+ly[j]-f[i][j]);
	for (i=1;i<=t;i++) if (S[i]) lx[i]-=a;
	for (i=1;i<=t;i++) if (T[i]) ly[i]+=a;
	return ;
}
int KM(){
	int i,j,ans=0;
	memset(lef,0,sizeof(lef));
	memset(lx,-62,sizeof(lx));	memset(ly,0,sizeof(ly));
	for (i=1;i<=t;i++)
		for (j=1;j<=t;j++)
			lx[i]=max(lx[i],f[i][j]);
	for (i=1;i<=t;i++)
		for (;;){
			memset(S,0,sizeof(S));memset(T,0,sizeof(T));
			if (match(i)) break;
			update();
		}
	for (i=1;i<=t;i++) ans+=f[lef[i]][i];
	return ans;
}
int main(){
	scanf("%d %d",&n,&m);
	while (n!=0){
		for (i=0;i<n;i++) scanf("%s",a[i]);
		t=w=0;
		for (i=0;i<n;i++)
			for (j=0;j<m;j++)
				if (a[i][j]=='H') b[++t].x=i,b[t].y=j;
				else if (a[i][j]=='m') c[++w].x=i,c[w].y=j;
		for (i=1;i<=t;i++)
			for (j=1;j<=t;j++)
				f[i][j]=-abs(b[i].x-c[j].x)-abs(b[i].y-c[j].y);
		printf("%d\n",-KM());	
		scanf("%d %d",&n,&m);		
	}
	return 0;
}

题目点这里 样例都没过.....

2021/2/22 19:28
加载中...