思想和分治凸包算法很像。
把生成树的((sum_x,sum_y))投射到平面上，我们要找到((x,y))使得(x,y)最小。
可以证明，最优的((x,y))在凸包上。
证明可见2018国集论文。
考虑怎么求凸包，可以分治，保证当前处理的((l,r))是凸包上的连续一段。
先求出凸包的最左/最右点，设为(A,B)这可以用两次mst，我们只需要对(sum_x,sum_y) mst即可。
考虑凸包上每个点向(AB)作垂线。
假设(C)到(AB)的距离最大，则(C)一定在凸包上，可以递归((A,C),(C,B))处理。
考虑如何求出(C)，这相当于求出(C)使得三角形(ABC)的大小最大。
考虑叉积，我们要最小化(AB imes AC)
推出式子后发现这是((x_B-x_A)y_C+(y_A-y_B)x_C-(x_B-x_A)y_A+(y_B-y_A)x_A)
(-(x_B-x_A)y_A+(y_B-y_A)x_A)只要知道(A,B)后就能求出。
((x_B-x_A)y_C+(y_A-y_B)x_C)，可以把每条边的权值设为((x_B-x_A)b_i+(y_A-y_B)a_i)，求mst。
时间复杂度比较玄学
#include<bits/stdc++.h>
using namespace std;
#define N 20010
#define int long long
int n,m,f[N];
struct no{
int x,y,w,a,b;
}a[N];
int operator<(no x,no y){
return x.w<y.w;
}
struct nn{
int x,y;
}va;
int operator^(nn x,nn y){
return x.x*y.y-x.y*y.x;
}
nn operator+(nn x,nn y){
return ((nn){x.x+y.x,x.y+y.y});
}
nn operator-(nn x,nn y){
return ((nn){x.x-y.x,x.y-y.y});
}
int fd(int x){
return !f[x]?x:f[x]=fd(f[x]);
}
nn mst(){
sort(a+1,a+m+1);
nn ans;
ans.x=ans.y=0;
for(int i=1;i<=n;i++)
f[i]=0;
for(int i=1;i<=m;i++){
int xx=fd(a[i].x),yy=fd(a[i].y);
if(xx!=yy){
f[xx]=yy;
ans.x+=a[i].a;
ans.y+=a[i].b;
}
}
if(ans.x*ans.y<va.x*va.y)
va=ans;
else if(ans.x*ans.y==va.x*va.y&&ans.x>va.x)
va=ans;
return ans;
}
void fz(nn A,nn B){
for(int i=1;i<=m;i++)
a[i].w=(B.x-A.x)*a[i].b+(A.y-B.y)*a[i].a;
nn C=mst();
if(((B-A)^(C-A))>=0)
return;
fz(A,C);
fz(C,B);
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].a,&a[i].b);
a[i].x++;
a[i].y++;
}
va.x=va.y=1e9;
for(int i=1;i<=m;i++)
a[i].w=a[i].a;
nn A=mst();
for(int i=1;i<=m;i++)
a[i].w=a[i].b;
nn B=mst();
fz(A,B);
printf("%lld %lld",va.x,va.y);
}
HNOI2014 画框
考虑上面那题的算法。
我们要求一组匹配，使得((sum A)*(sum B))最小。
考虑求出((sum A,sum B))构成的下凸包。
求出凸包最左/最右点可以把((i,j))的边权设为(a_{i,j})然后最小权匹配。
求出(C)点事实上是最小化((x_B-x_A)y_C+(y_A-y_B)x_C)
把一条边的权值设为((x_B-x_A)y_C+(y_A-y_B)x_C)然后最小权匹配即可。
可以把边权取反后最大权匹配
#include<bits/stdc++.h>
using namespace std;
#define N 110
#define int long long
int n,w[N][N],x[N][N],y[N][N],t[N],va,vx[N],vy[N],a[N],b[N],sl;
struct nn{
int x,y;
};
int operator^(nn x,nn y){
return x.x*y.y-x.y*y.x;
}
nn operator+(nn x,nn y){
return ((nn){x.x+y.x,x.y+y.y});
}
nn operator-(nn x,nn y){
return ((nn){x.x-y.x,x.y-y.y});
}
int dfs(int x){
vx[x]=1;
for(int i=1;i<=n;i++)
if(!vy[i]){
if(a[x]+b[i]==w[x][i]){
vy[i]=1;
if(!t[i]||dfs(t[i])){
t[i]=x;
return 1;
}
}
else sl=min(sl,a[x]+b[i]-w[x][i]);
}
return 0;
}
nn km(){
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++){
b[i]=a[i]=0;
for(int j=1;j<=n;j++)
a[i]=max(a[i],w[i][j]);
}
for(int i=1;i<=n;i++){
while(1){
memset(vx,0,sizeof(vx));
memset(vy,0,sizeof(vy));
sl=1e9;
if(dfs(i))break;
for(int j=1;j<=n;j++){
if(vx[j])
a[j]-=sl;
if(vy[j])
b[j]+=sl;
}
}
}
nn ans;
ans.x=ans.y=0;
for(int i=1;i<=n;i++){
ans.x+=x[t[i]][i];
ans.y+=y[t[i]][i];
}
va=min(va,ans.x*ans.y);
return ans;
}
void fz(nn A,nn B){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=-((A.y-B.y)*x[i][j]+(B.x-A.x)*y[i][j]);
nn C=km();
if(((B-A)^(C-A))>=0)
return;
fz(A,C);
fz(C,B);
}
signed main(){
int T;
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&x[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&y[i][j]);
va=1e18;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=-x[i][j];
nn A=km();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
w[i][j]=-y[i][j];
nn B=km();
fz(A,B);
printf("%lld
",va);
}
}