题解 洛谷 P3236 [HNOI2014]画框
题意描述
给定一张每边 \(n\) 个点的完全二分图，每条边有权值 \(A_{i,j}\) 和 \(B_{i,j}\) ，选择完美匹配 \(E\) ，求 \(\min\{\sum\limits_{p_i\in E}A_{i,p_i}\times\sum\limits_{p_i\in E}B_{i,p_i}\}\)
\(n\leq 70,A_{i,j},B_{i,j}\leq200\)
多组数据
单独求出权值为 \(A\) 和权值为 \(B\) 都很简单，就是最小权完美匹配，不过完全二分图上跑 \(EK\) 很慢，要用 \(KM\) 或 \(zkw\) 。
如果我们把一个匹配的权值 \(A\) 和权值 \(B\) 抽象到二维平面上的点，显然，在两点之间连线以上的点答案没有两端优。于是我们先求出以 \(A\) 为边权的答案和以 \(B\) 为边权的答案，放到平面直角坐标系中。
对于在直线 \(AB\) 下方的点，设为 \(C\) ，则所有最优的 \(C\) 形成一个下凸壳，最终答案就是所有下凸壳上的点的横纵坐标之积的最小值。
考虑用计算几何中的叉积求 \(C\) ：
设 \(A(x_A,y_A),B(x_B,y_B),C(x_C,y_C)\) ，则 \(\Delta ABC\) 的叉积 \(<0\) 时， \(C\) 在直线 \(AB\) 下方，即 \(\overrightarrow{AB}\times\overrightarrow{AC}<0\) ，还可以发现， \(\Delta ABC\) 的叉积越小， \(x_C\times y_C\) 越小。
推推式子：
\(\begin{aligned}Ans&=\min\{(x_A-x_B,y_A-y_B)\times(x_A-x_C,y_A-y_C)\}\\&=\min\{(x_A-x_B)\times(y_A-y_C)-(x_A-x_C)\times(y_A-y_B)\}\\&=\min\{x_A\times y_A-x_A\times y_C-x_B\times y_A+x_B\times y_C-x_A\times y_A+x_A\times y_B+x_C\times y_A-x_C\times y_B\}\\&=\min\{(y_A-y_B)\times x_C+(x_B-x_A)\times y_C+x_A\times y_B-x_B\times y_A\}\end{aligned}\)
后面两项是定值，所以我们只要最小化 \((y_A-y_B)\times x_C+(x_B-x_A)\times y_C\) 即可。将 \((y_A-y_B)\times A_{i,j},(x_B-x_A)\times B_{i,j}\) 作为新的边权，再跑一遍最小权完美匹配，得到的答案就是点 \(C\) 。递归求出答案即可。
注意最小权完美匹配所有值都要取反，（包括 \(y_A-y_B\) 和 \(x_B-x_A\) ，笔者因为这个调了好久……）
代码如下：
#include<bits/stdc++.h>
#define int long long
#define inf 1e15
#define N 75
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define il inline
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
il int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
struct Vector{
int x,y;
Vector operator-(const Vector&p){return (Vector){x-p.x,y-p.y};}
int operator*(const Vector&p){return(x*p.y-y*p.x);}
};
int n,A[N][N],B[N][N],ans=inf;
namespace KM{
int w[N][N];
int vl[N],vr[N];
int visl[N],visr[N];
int used[N];
bool dfs(int u){
visl[u]=1;
for(int i=1;i<=n;i++){
if(!visr[i]){
if(vl[u]+vr[i]==w[u][i]){
visr[i]=1;
if(!used[i]||dfs(used[i])){
used[i]=u;
return true;
}
}
}
}
return false;
}
void KM(){
for(int i=1;i<=n;i++){
while(true){
for(int i=1;i<=n;i++)visl[i]=visr[i]=0;
if(dfs(i))break;
int mn=inf;
for(int j=1;j<=n;j++)
if(visl[j])
for(int k=1;k<=n;k++)
if(!visr[k])
mn=min(mn,vl[j]+vr[k]-w[j][k]);
for(int j=1;j<=n;j++)if(visl[j])vl[j]-=mn;
for(int j=1;j<=n;j++)if(visr[j])vr[j]+=mn;
}
}
}
void init(int valA,int valB){
for(int i=1;i<=n;i++)used[i]=vl[i]=vr[i]=0;
for(int i=1;i<=n;i++){
int mx=0;
for(int j=1;j<=n;j++){
w[i][j]=-(A[i][j]*valA+B[i][j]*valB);
mx=max(mx,w[i][j]);
}
vl[i]=mx;
}
}
Vector calc(){
KM();
Vector ans=(Vector){0,0};
for(int i=1;i<=n;i++)
ans.x-=A[used[i]][i],ans.y-=B[used[i]][i];
return ans;
}
}
void work(Vector X,Vector Y){
int valA=Y.y-X.y,valB=X.x-Y.x;
KM::init(valA,valB);
Vector Z=KM::calc();
ans=min(ans,Z.x*Z.y);
if((Y-X)*(Z-X)>=0)return;
work(X,Z);work(Z,Y);
}
void solve(){
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();
KM::init(1,0);
Vector X=KM::calc();
KM::init(0,1);
Vector Y=KM::calc();
ans=min(X.x*X.y,Y.x*Y.y);
work(X,Y);
printf("%lld\n",ans);
}
signed main(){
int T=read();
while(T--)solve();
return 0;
}