自动搬运

查看原文

来自洛谷，原作者为

	xfrvq **

搬运于2025-08-24 21:46:48，当前版本为作者最后更新于2025-08-19 15:55:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对每种匹配方式，将其看做平面上一点 $(\sum A_{i,p_i},\sum B_{i,p_i})$，显然答案在点集左下凸包上。

无法直接求出凸包，先分别求出点 $A$：使 $\sum A_{i,p_i}$ 最小，不管 $\sum B$。点 $B$ 同理。这两个点一定是左下凸包的两端。

接下来是一个递归算法：求出到直线 $AB$ 左下距离最远的点 $C$，然后递归做直线 $AC,BC$。即最小化 $\overrightarrow{AB}\times \overrightarrow{AC}=(x_B-x_A)y_C+(y_A-y_B)x_C+y_Bx_A-x_By_A$。

即最小化 $(y_A-y_B)\sum A_{i,p_i}+(x_B-x_A)\sum B_{i,p_i}$。那么将一对匹配权值改为 $(y_A-y_B)A_{i,j}+(x_B-x_A)B_{i,j}$，做二分图最小权完美匹配即可。

边界条件：若找不到 $C$（$C$ 不在 $AB$ 左下）则停止。

MCMF 卡常技巧

• 链式前向星，将 $v,w,c$ 存在结构体内，$nxt$ 单独开数组。
• SPFA 时手写队列，并使用 SLF 优化：往队列加入点 $v$ 时，若 dis[v]<dis[q.front()] 则 push_front 否则 push_back。
• 每次网络流完，在原图复原流量，而不是重新建图。

// C++98
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pr;

#define x first 
#define y second
#define rep(i,a,b) for(int i = (a);i <= (b);++i)

#ifdef ONLINE_JUDGE
static char buf[2097152],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,2097152,stdin),p1==p2)?EOF:*p1++
#endif

inline int read(){
    register int x = 0;
    register char c = getchar();
    for(;c < '0' || c > '9';c = getchar());
    for(;c >= '0' && c <= '9';c = getchar())
        x = x * 10 + (c ^ '0');
    return x;
}

const int N = 145,M = 12005,inf = 0x3f3f3f3f;

int T,n,a[N][N],b[N][N],st,ed,ans;

struct edge{ int v,w,c; } E[M]; int nxt[M];

int Etot = 1,from[N];

void add(int u,int v,int w,int c){
	E[++Etot] = (edge){v,w,c}; nxt[Etot] = from[u]; from[u] = Etot;
    E[++Etot] = (edge){u,0,-c}; nxt[Etot] = from[v]; from[v] = Etot;
}

int Q[N * 5],pnt[N];
int dis[N],now[N]; bool vis[N];

int SPFA(){
    int L = N,R = N - 1; Q[++R] = st;
    for(int i = 0;i <= ed;++i) dis[i] = inf;
    dis[st] = 0;
    while(L <= R){
        int u = Q[L++];
        vis[u] = 0;
        for(int i = now[u] = from[u];i;i = nxt[i]){
            int v = E[i].v,w = E[i].w,c = E[i].c;
            if(w && dis[v] > dis[u] + c){
                dis[v] = dis[u] + c;
                if(!vis[v]){
                    vis[v] = 1;
                    if(L > R || dis[v] > dis[Q[L]]) Q[++R] = v;
                    else Q[--L] = v;
                }
            }
        }
    }
    return dis[ed] < inf;
}

int dfs(int u,int fl){
	if(u == ed) return fl;
	vis[u] = 1;
	int v,k,cnt = 0;
    for(int i = now[u];i;i = nxt[i]){
        now[u] = i;
    	v = E[i].v;
    	if(E[i].w > 0 && dis[v] == dis[u] + E[i].c && !vis[v]){
    		k = dfs(v,min(fl,E[i].w));
    		if(u <= n && k) pnt[u] = v - n;
    		E[i].w -= k,E[i ^ 1].w += k;
    		cnt += k,fl -= k;
    		if(!fl) break;
			if(!k) dis[v] = -1;
		}
	}
	vis[u] = 0;
	return cnt;
}

pr mcmf(int x,int y){
	int k = 0;
	rep(i,1,n) rep(j,1,n) k += 2,E[k].c = x * a[i][j] + y * b[i][j],E[k ^ 1].c = -E[k].c;
	while(SPFA()) dfs(st,inf);
	int sa = 0,sb = 0;
	rep(i,1,n){
		sa += a[i][pnt[i]],sb += b[i][pnt[i]];
		int k = ((i - 1) * n + pnt[i]) * 2;
		E[k].w = 1,E[k ^ 1].w = 0;
	}
	rep(i,1,2 * n) k += 2,E[k].w = 1,E[k ^ 1].w = 0;
	ans = min(ans,sa * sb);
	return pr(sa,sb);
}

pr operator-(const pr &a,const pr& b){ return pr(a.x - b.x,a.y - b.y); } 

int cross(pr a,pr b){ return a.x * b.y - a.y * b.x; }

void sol(pr a,pr b){
	pr c = mcmf(a.y - b.y,b.x - a.x);
	if(cross(b - a,c - a) < 0) sol(a,c),sol(c,b);
} 

int main(){
	for(T = read();T--;){
		n = read(),ed = 2 * n + 1,ans = 1e9;
		rep(i,1,n) rep(j,1,n) add(i,j + n,1,a[i][j] = read());
		rep(i,1,n) rep(j,1,n) b[i][j] = read();
		rep(i,1,n) add(st,i,1,0),add(i + n,ed,1,0);
		pr a = mcmf(1,0);
		pr b = mcmf(0,1);
		sol(a,b);
		printf("%d\n",ans);
		Etot = 1;
		for(int i = 0;i <= ed;++i) from[i] = 0;
	}
	return 0;
}