RT，蒟蒻不会 KM 只会费用流。最后一个点开了 O2 后在 2.01s~2.03s，求大佬帮忙卡常。

如果有什么优化方法也可以的。

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=233,inf=1e9+7;

inline int read(){
    char ch=getchar(); int f=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') f=f*10+ch-'0',ch=getchar();
    return f;
}
inline int min(int A,int B){return A<B?A:B;}

int T,n,A[71][71],B[71][71];

int head[M],cnte=1;
struct Edge{int to,nxt,flow,cap,cost;}e[160*160];
void add(int u,int v,int w,int c){
    e[++cnte]=(Edge){v,head[u],0,w,c};
    head[u]=cnte;
}
void addedge(int u,int v,int w,int c){
    //printf("add(%d,%d)\n",u,v);
    add(u,v,w,c),add(v,u,0,-c);
}

int s,t;
void build(){
    for(int i=1;i<=n;i++) addedge(s,i,0,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) addedge(i,j+n,0,0);
    for(int j=1;j<=n;j++) addedge(j+n,t,0,0);
}
void rebuild(int P,int Q){
    for(int i=head[s];~i;i=e[i].nxt){
        e[i].cap=1,e[i].flow=0,e[i].cost=0;
        e[i^1].cap=0,e[i^1].flow=0,e[i^1].cost=0;
    }
    for(int u=1;u<=n;u++)
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].to; if(v==s) continue;
            e[i].cap=1,e[i].flow=0,e[i].cost=P*A[u][v-n]+Q*B[u][v-n];
            e[i^1].cap=0,e[i^1].flow=0,e[i^1].cost=-e[i].cost;
        }
    for(int i=head[t];~i;i=e[i].nxt){
        e[i].cap=0,e[i].flow=0,e[i].cost=0;
        e[i^1].cap=1,e[i^1].flow=0,e[i^1].cost=0;
    }
}

int infl[M],dis[M],pre[M]; bool inq[M];
bool SPFA(){
    for(int i=s;i<=t;i++) infl[i]=dis[i]=inf;
    queue<int>q; q.push(s),dis[s]=0,inq[s]=true;
    while(!q.empty()){
        int u=q.front(); q.pop(),inq[u]=false;
        //printf("SPFA: u = %d\n",u);
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].to;
            //printf("SPFA: (%d,%d) cost=%d dis[%d]=%d\n",u,v,e[i].cost,v,dis[v]);
            if(e[i].cap>e[i].flow && dis[v]>dis[u]+e[i].cost){
                pre[v]=i,infl[v]=min(infl[u],e[i].cap-e[i].flow);
                dis[v]=dis[u]+e[i].cost;
                if(!inq[v]) inq[v]=true,q.push(v);
            }
        }
    }
    return dis[t]!=inf;
}
int MCMF(){
    int cost=0;
    while(SPFA()){
        cost+=infl[t]*dis[t]; int cur=t;
        while(cur!=s){
            e[pre[cur]].flow+=infl[t];
            e[pre[cur]^1].flow-=infl[t];
            cur=e[pre[cur]^1].to;
        }
    }
    //printf("cost = %d\n",cost);
    return cost;
}

struct Vector{
    int x,y;
    Vector(int _x=0,int _y=0):x(_x),y(_y){}
    //Vector operator+(const Vector &o)const{return Vector(x+o.x,y+o.y);}
    Vector operator-(const Vector &o)const{return Vector(x-o.x,y-o.y);}
};
int cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

int ans;
void solve(Vector D,Vector E){
    rebuild(D.y-E.y,E.x-D.x),MCMF();
    Vector F;
    for(int u=1;u<=n;u++)
        for(int i=head[u];~i;i=e[i].nxt){
            int v=e[i].to; if(v==s) continue;
            if(e[i].cap<=e[i].flow) F.x+=A[u][v-n],F.y+=B[u][v-n];
        }
    if(cross(E-D,F-D)>=0) return;
    ans=min(ans,F.x*F.y);
    solve(D,F),solve(F,E);
}

void clear(){
    ans=inf,cnte=1;
    for(int i=s;i<=t;i++) head[i]=-1;
    for(int i=2;i<=cnte;i++)
        e[i].to=e[i].nxt=e[i].cap=e[i].flow=e[i].cost=0;
}

int main(){
    T=read(),s=0,t=M-1;
    while(T--){
        clear();
        n=read();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) A[i][j]=read();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) B[i][j]=read();
        
        s=0,t=2*n+1,build();
        rebuild(1,0),MCMF();
        Vector D,E;
        for(int u=1;u<=n;u++)
            for(int i=head[u];~i;i=e[i].nxt){
                int v=e[i].to; if(v==s) continue;
                if(e[i].cap<=e[i].flow) D.x+=A[u][v-n],D.y+=B[u][v-n];
            }
        //printf("D:(%d,%d)\n",D.x,D.y);
        rebuild(0,1),MCMF();
        for(int u=1;u<=n;u++)
            for(int i=head[u];~i;i=e[i].nxt){
                int v=e[i].to; if(v==s) continue;
                if(e[i].cap<=e[i].flow) E.x+=A[u][v-n],E.y+=B[u][v-n];
            }
        ans=min(ans,min(D.x*D.y,E.x*E.y));
        solve(D,E);
        printf("%d\n",ans);
    }
    return 0;
}