值得一写的脑洞题!
最开始没有任何思路，看了题解后才会做。
考虑将a的和与b的和表示为坐标，那么可能为答案的点一定是下凸包中的点，这样优化枚举就保证了效率。
然而并不知道到底哪些点是凸包中的点，但我们知道边界的两点（a最小于b最小）一定在凸包上，如果已知两个凸包上的点，我们将它们连线，那么属于原图中的点若距离此直线最远，则一定是凸包上的点，于是可以二分，用向量的叉积求出那个点。
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=120; 6 const int INF=1147483647; 7 int a[maxn][maxn],b[maxn][maxn]; 8 int w[maxn][maxn],sx[maxn],sy[maxn]; 9 int mat[maxn],sla[maxn];10 int lx[maxn],ly[maxn];11 int n,T;12 struct Dot{13 int x,y;14 Dot(int x_=0,int y_=0):x(x_),y(y_){}15 friend bool operator ==(Dot a,Dot b){16 return a.x==b.x&&a.y==b.y;17 }18 }lo,hi;19 bool DFS(int x){20 sx[x]=1;21 for(int y=1;y<=n;y++)22 if(!sy[y]){23 int t=lx[x]+ly[y]-w[x][y];24 if(t)sla[y]=min(sla[y],t);25 else{26 sy[y]=1;27 if(!mat[y]||DFS(mat[y]))28 {mat[y]=x;return true;}29 } 30 }31 return false; 32 }33 34 Dot KM(){35 memset(lx,0,sizeof(lx));36 memset(ly,0,sizeof(ly));37 memset(mat,0,sizeof(mat));38 for(int i=1;i<=n;i++)39 for(int j=1;j<=n;j++)40 lx[i]=max(lx[i],w[i][j]);41 42 for(int x=1;x<=n;x++){43 memset(sla,63,sizeof(sla));44 while(true){45 memset(sx,0,sizeof(sx));46 memset(sy,0,sizeof(sy));47 if(DFS(x))break;48 int Min=INF;49 for(int i=1;i<=n;i++)if(!sy[i])Min=min(Min,sla[i]);50 for(int i=1;i<=n;i++){51 if(sx[i])lx[i]-=Min;52 sy[i]?ly[i]+=Min:sla[i]-=Min;53 }54 }55 }56 Dot ret(0,0);57 for(int i=1;i<=n;i++){58 ret.x+=a[mat[i]][i];59 ret.y+=b[mat[i]][i];60 }61 return ret; 62 }63 64 int Solve(Dot l,Dot r){65 for(int i=1;i<=n;i++)66 for(int j=1;j<=n;j++)67 w[i][j]=a[i][j]*(r.y-l.y)-b[i][j]*(r.x-l.x);68 Dot mid=KM();69 if(mid==l||mid==r)return min(l.x*l.y,r.x*r.y);70 return min(Solve(l,mid),Solve(mid,r));71 }72 73 74 int main(){75 freopen("frame.in","r",stdin);76 freopen("frame.out","w",stdout);77 scanf("%d",&T);78 while(T--){79 scanf("%d",&n);80 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]); 81 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&b[i][j]); 82 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)w[i][j]=-a[i][j];lo=KM();83 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)w[i][j]=-b[i][j];hi=KM();84 printf("%d\n",Solve(lo,hi));85 }86 return 0;87 }