题面

题解

我似乎连\(KM\)都不会打啊→_→

和是一样的，只不过把最小生成树换成\(KM\)了。因为\(KM\)跑的是最大权值所以取个反就行了

//minamoto#include
    
     #define R register#define inf 0x3f3f3f3f#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}template
       
        inline bool cmax(T&a,const T&b){return a
        
         '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=105;struct node{    int x,y;    node(){}    node(R int xx,R int yy):x(xx),y(yy){}    inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}    inline int operator *(const node &b)const{return x*b.y-y*b.x;}    inline bool operator >(const node &b)const{return x*y>b.x*b.y;}}ma,mb,res;int g[N][N],a[N][N],b[N][N],vx[N],vy[N],mt[N],lx[N],ly[N];int n,d,cnt;bool dfs(int x){    vx[x]=cnt;    fp(y,1,n)if(vy[y]!=cnt)        if(lx[x]+ly[y]==g[x][y]){            vy[y]=cnt;            if(!mt[y]||dfs(mt[y]))return mt[y]=x,true;        }else cmin(d,lx[x]+ly[y]-g[x][y]);    return false;}node KM(){    fp(i,1,n)lx[i]=-inf,ly[i]=mt[i]=0;    fp(i,1,n)fp(j,1,n)cmax(lx[i],g[i][j]);    fp(x,1,n)while(++cnt,d=inf,!dfs(x)){        fp(i,1,n){            if(vx[i]==cnt)lx[i]-=d;            if(vy[i]==cnt)ly[i]+=d;        }    }    node P(0,0);    fp(i,1,n)P.x+=a[mt[i]][i],P.y+=b[mt[i]][i];    return cmin(res,P),P;}void solve(node A,node B){    fp(i,1,n)fp(j,1,n)g[i][j]=-(b[i][j]*(B.x-A.x)-a[i][j]*(B.y-A.y));    node C=KM();    if((B-A)*(C-A)>=0)return;    solve(A,C),solve(C,B);}void MAIN(){    n=read(),res=node(inf,inf);    fp(i,1,n)fp(j,1,n)a[i][j]=read();    fp(i,1,n)fp(j,1,n)b[i][j]=read();    fp(i,1,n)fp(j,1,n)g[i][j]=-a[i][j];    ma=KM();    fp(i,1,n)fp(j,1,n)g[i][j]=-b[i][j];    mb=KM();    solve(ma,mb);    printf("%d\n",res.x*res.y);}int main(){//  freopen("testdata.in","r",stdin);    for(int T=read();T;--T)MAIN();    return 0;}