洛谷 P3236 题解

思路分析

我们把每一个决策（匹配） $p$ 看成一个二维平面上的点 $(X_p,X_p)$，其中 $X_p=\sum_{i=1}^n A_{i,p_i}$，$Y_p=\sum_{i=1}^n B_{i,p_i}$

我们要找到最小的 $X_p\times Y_p$ ，有一个显然的优化：对于两个决策 $p_1,p_2$，如果 $X_{p_1}\le X_{p_2}$ 且 $Y_{p_1}\le Y_{p_2}$ 那么 $p_2$ 肯定是不优的，因此剪枝之后我们需要维护的 $p$ 在二维平面上一定构成一个下凸壳 $\mathbf H$

对于 $\mathbf H$ 最左边的点 $A$ 和最右边的点 $B$ 应该是显然的：就是最小化 $X_p$ 和最小化 $_p$ Y得到的两个决策

显然，在 $AB$ 下方可以找到一个点 $C$ 并且最大化 $C$ 到 $AB$ 的距离，那么此时的 $C$ 一定在 $\mathbf H$ 上，那么我们就可以对 $AC$，$BC$ 分别分治了

问题转化为求 $C$，首先考虑过 $AB$ 的一条直线 $(Y_A-Y_B)\times x+(X_B-X_A)\times y=X_B\times Y_A-X_A\times Y_B$

不妨记 $F_{AB}(x,y)=(Y_A-Y_B)\times x+(X_B-X_A)\times y$，原直线方程变为 $F_{AB}(x,y)=F_{AB}(A_X,A_Y)$

接下来考虑与 $AB$ 平行且过某一点 $P$ 的直线 $F_{AB}(x,y)=F_{AB}(P_X,P_Y)$，显然我们只需要最大化 $F_{AB}(A_X,A_Y)-F_{AB}(P_X,P_Y)$ 即可得到 $C$

所以我们只需要把每条边 $E_{i,j}$ 的边权设置为 $A_{i,j}\times(Y_A-Y_B)+B_{i,j}\times(X_B-X_A)$，然后求出新二分图的最小权完美匹配即可

使用 KM 解决此问题，时间复杂度 $\Theta(|\mathbf H|n^3)$，其中 $|\mathbf H|$ 为维护的凸壳的总大小

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=71,INF=1e18,MAXV=3e6;
int n,ans;
struct point {
	int x,y;
	point() { x=0,y=0; }
	inline int calc(point A,point B) {
		return x*(A.y-B.y)+(B.x-A.x)*y;
	}
};
struct B_graph {
	int a[MAXN][MAXN],b[MAXN][MAXN];
	int w[MAXN][MAXN],lx[MAXN],ly[MAXN],slack[MAXN],tar[MAXN];
	bool sx[MAXN],sy[MAXN];
	inline void Read() {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				scanf("%lld",&a[i][j]);
			}
		}
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				scanf("%lld",&b[i][j]);
			}
		}
	}
	inline bool find(int x) {
		if(sx[x]) return false;
		sx[x]=true;
		for(int y=1;y<=n;++y) {
			if(sy[y]) continue;
			int k=lx[x]+ly[y]-w[x][y];
			if(!k) {
				sy[y]=true;
				if(tar[y]==-1||find(tar[y])) {
					tar[y]=x;
					return true;
				}
			} else slack[y]=min(slack[y],k);
		}
		return false;
	}
	inline point MM(int cx,int cy) {
		memset(tar,-1,sizeof(tar));
		memset(lx,0,sizeof(lx));
		memset(ly,0,sizeof(ly)); 
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				w[i][j]=MAXV-(a[i][j]*cx+b[i][j]*cy);
				lx[i]=max(lx[i],w[i][j]);
			}
		}
		for(int t=1;t<=n;++t) {
			memset(slack,0x3f,sizeof(slack));
			memset(sx,false,sizeof(sx));
			memset(sy,false,sizeof(sy));
			if(find(t)) continue;
			while(true) {
				int delta=INF,y=0;
				for(int i=1;i<=n;++i) if(!sy[i]) delta=min(delta,slack[i]);
				for(int i=1;i<=n;++i) {
					if(sx[i]) lx[i]-=delta;
					if(sy[i]) ly[i]+=delta;
					else {
						slack[i]-=delta;
						if(!slack[i]) y=i;
					}
				}
				if(tar[y]==-1) break;
 				int x=tar[y];
 				sx[x]=true,sy[y]=true;
 				for(int i=1;i<=n;++i) slack[i]=min(slack[i],lx[x]+ly[i]-w[x][i]);
			}
			memset(sx,false,sizeof(sx));
			memset(sy,false,sizeof(sy));
			find(t);
		}
		point ret;
		for(int i=1;i<=n;++i) {
			ret.x+=a[tar[i]][i];
			ret.y+=b[tar[i]][i];
		}
		return ret;
	}
}	G;
inline void solve(point A,point B) {
	point C=G.MM(A.y-B.y,B.x-A.x);
	ans=min(C.x*C.y,ans);
	if(C.calc(A,B)>=A.calc(A,B)) return ;
	solve(A,C); solve(C,B); 
}
signed main() {
	int T;
	scanf("%lld",&T);
	while(T--) {
		scanf("%lld",&n);
		G.Read();
		point A=G.MM(1,0),B=G.MM(0,1);
		ans=min(A.x*A.y,B.x*B.y);
		solve(A,B);
		printf("%lld\n",ans);
	}
	return 0;
}