C++ 解法, 执行用时: 217ms, 内存消耗: 464K, 提交时间: 2021-11-16 16:57:15

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
 
struct node{
	int x,y;
	bool operator ==(const node q)const{
		return x==q.x && y==q.y;
	}
};
int T,n;
int a[75][75],b[75][75];
int g[75][75];
int tx[75],ty[75];
bool visx[75],visy[75];
int prep[75];
 
bool find(int x){
	visx[x]=true;
	for(int i=1;i<=n;i++)
		if(!visy[i] && tx[x]+ty[i]==g[x][i]){
			visy[i]=true;
			if(prep[i]==0 || find(prep[i])){
				prep[i]=x;
				return true;
			}
		}
	return false;
}
 
node KM(){
	memset(tx,0,sizeof(tx));
	memset(ty,0,sizeof(ty));
	memset(prep,0,sizeof(prep));
	int mmin=1e9;
	for(int i=1;i<=n;i++){
		while(1){
			memset(visx,false,sizeof(visx));
			memset(visy,false,sizeof(visy));
			if(find(i)) break;
			mmin=1e9;
			for(int j=1;j<=n;j++) if(visx[j])
				for(int k=1;k<=n;k++) if(!visy[k]) mmin=min(mmin,tx[j]+ty[k]-g[j][k]);
			for(int j=1;j<=n;j++) if(visx[j]) tx[j]-=mmin;
			for(int j=1;j<=n;j++) if(visy[j]) ty[j]+=mmin;
		}
	}
	node op=(node){0,0};
	for(int i=1;i<=n;i++) op.x+=a[prep[i]][i],op.y+=b[prep[i]][i];
	return op;
}
 
int solve(node left,node right){
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++)
			g[i][j]=(right.y-left.y)*a[i][j]+(left.x-right.x)*b[i][j];
	node mid=KM();
	if(left==mid || mid==right) return min(left.x*left.y,right.x*right.y);
	return min(solve(left,mid),solve(mid,right));
}
 
int main(){
	scanf("%d",&T);
	node left,right;
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=n;j++) 
				scanf("%d",&a[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&b[i][j]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]=-a[i][j];
		left=KM();
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=n;j++)
				g[i][j]=-b[i][j];
		right=KM();
		printf("%d\n",solve(left,right));
    }
}