我们把一种方案的(sum a_{i,j})和(sum b_{i,j})看成点((sum a_{i,j},sum b_{i,j})),那么就只要求横纵坐标之积最小的点,类似于最小乘积生成树
首先跑出(sum a_{i,j})最小和(sum b_{i,j})最小的,得到的点记为(A)和(B),然后求一个在(AB)左侧,距离(AB)最远的点(C).这就相当于要最大化(S_{ riangle ABC}=|frac{vec{AB} imesvec{AC}}{2}|),因为(C)在(AB)左侧,所以是要最小化
[egin{matrix}vec{AB} imesvec{AC} &= (x_B-x_A)*(y_C-y_A)-(y_B-y_A)*(x_C-x_A)\ &= (x_B-x_A)*y_C+(y_A-y_B)*x_C+Send{matrix}
]
((S为常数项))
所以把((x_B-x_A)*b_{i,j}+(y_A-y_B)*a_{i,j})设为边权,跑KM就好了,如果找到这样的点就继续递归处理(AC)和(CB),注意如果叉积(ge 0),那么不在左侧,退出
话说二分图最小权匹配只要边权取反就好了,我沙雕还把其他地方跟着改了,WA的捕星
#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register
using namespace std;
const int N=75;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,a[N][N],b[N][N],mat[N],va[N],vb[N],e[N][N],sl[N],pr[N];
bool v[N];
void xyl(int xx)
{
memset(sl,0x3f3f3f,sizeof(sl));
memset(v,0,sizeof(v));
memset(pr,0,sizeof(pr));
int p=0;
mat[p]=xx;
do
{
int x=mat[p],mi=sl[0],nxt;
v[p]=1;
for(int y=1;y<=n;++y)
if(!v[y])
{
if(sl[y]>va[x]+vb[y]-e[x][y]) sl[y]=va[x]+vb[y]-e[x][y],pr[y]=p;
if(mi>sl[y]) mi=sl[y],nxt=y;
}
for(int i=0;i<=n;++i)
{
if(v[i]) va[mat[i]]-=mi,vb[i]+=mi;
else sl[i]-=mi;
}
p=nxt;
}while(mat[p]);
while(p) mat[p]=mat[pr[p]],p=pr[p];
}
int ans;
void dc(int ax,int ay,int bx,int by)
{
if(ay<by||(ay==by&&ax>bx)) swap(ax,bx),swap(ay,by);
int cx=0,cy=0;
for(int i=1;i<=n;++i)
{
va[i]=vb[i]=0;
for(int j=1;j<=n;++j)
va[i]=max(va[i],e[i][j]=-((bx-ax)*b[i][j]+(ay-by)*a[i][j]));
}
memset(mat,0,sizeof(mat));
for(int i=1;i<=n;++i) xyl(i);
for(int j=1;j<=n;++j) cx+=a[mat[j]][j],cy+=b[mat[j]][j];
ans=min(ans,cx*cy);
if((bx-ax)*(cy-ay)-(by-ay)*(cx-ax)<0) dc(ax,ay,cx,cy),dc(cx,cy,bx,by);
}
int main()
{
int T=rd();
while(T--)
{
n=rd();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=rd();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
b[i][j]=rd();
int ax=0,ay=0,bx=0,by=0;
for(int i=1;i<=n;++i)
{
va[i]=vb[i]=0;
for(int j=1;j<=n;++j)
va[i]=max(va[i],e[i][j]=-a[i][j]);
}
memset(mat,0,sizeof(mat));
for(int i=1;i<=n;++i) xyl(i);
for(int j=1;j<=n;++j) ax+=a[mat[j]][j],ay+=b[mat[j]][j];
for(int i=1;i<=n;++i)
{
va[i]=vb[i]=0;
for(int j=1;j<=n;++j)
va[i]=max(va[i],e[i][j]=-b[i][j]);
}
memset(mat,0,sizeof(mat));
for(int i=1;i<=n;++i) xyl(i);
for(int j=1;j<=n;++j) bx+=a[mat[j]][j],by+=b[mat[j]][j];
ans=min(ax*ay,bx*by);
dc(ax,ay,bx,by);
printf("%d
",ans);
}
return 0;
}