题解 P5540 【【模板】最小乘积生成树】

2019-08-30 19:53:15


没见过的话(大概)还是比较难的 qaq


我们可以把每棵生成树的 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 看做二维坐标 $(x,y)$ 。于是我们就相当于要找一个 $x\times y$ 最小的点。

这个东西可以分三步求:

求出与 $x$ 轴和 $y$ 轴最近的点

这个还是很简单的。

把 $a_i$ 作为边权,求出的最小生成树就是与 $x$ 轴最近的点。

把 $b_i$ 作为边权,求出的最小生成树就是与 $y$ 轴最近的点。

为了下面讲解的方便,设与 $x$ 轴最近的点为 $A$ ,与 $y$ 轴最近的点为 $B$ 。

找到一个在 $AB$ 的左下方且离 $AB$ 最远的点

可能有一点难度。

假设这个点是 $C$ ,那么大概是这个样子:

$$\scriptsize\color{gray}{\text{图片来自 hyj 的 blog}}$$

事实上, $C$ 就是在 $AB$ 的左下方且 $S_{\triangle ABC}$ 最大的点。

容易知道 $S_{\triangle ABC}=-\frac{\vec{AB}\times\vec{AC}}{2}$ 。于是我们只要最小化 $\vec{AB}\times\vec{AC}$ 即可。

推一推式子:

$$\begin{aligned}\vec{AB}\times\vec{AC}&=(x_B-x_A)(y_C-y_A)-(x_C-x_A)(y_B-y_A)\\&=(x_B-x_A)y_C-(x_B-x_A)y_A-(y_B-y_A)x_C+(y_B-y_A)x_A\\&=(x_B-x_A)y_C+(y_A-y_B)x_C-(x_B-x_A)y_A+(y_B-y_A)x_A\end{aligned}$$

后两项是常数,我们只需最小化前两项。于是将边权设为 $(x_B-x_A)b_i+(y_A-y_B)a_i$ ,然后求最小生成树即可。

递归处理 $AC$ 与 $BC$

把当前 $AC$ 和 $BC$ 拿去做第二步的过程即可。

当新算出的 $C$ 不在 $AB$ 的左下方时就可以终止了。


建议画图并结合代码理解一下。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char a=getchar();
    while (a<'0'||a>'9') { if (a=='-') w=-1; a=getchar(); }
    while (a>='0'&&a<='9') X=X*10+a-'0',a=getchar();
    return X*w;
}

const int N=200+10;
const int M=10000+10;
const int inf=0x3f3f3f3f;

struct UFS { //并查集
    int f[N];
    inline void init(int n) { for (re int i=1;i<=n;++i) f[i]=i; }
    inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
    inline void merge(int x,int y) { x=find(x),y=find(y); if (x!=y) f[x]=y; }
    inline int check(int x,int y) { return find(x)==find(y); }
};

struct Edge { int u,v,w,a,b; };
inline int cmp(Edge a,Edge b) { return a.w<b.w; }

//计算几何相关
struct Point { int x,y; };
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }
inline int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }

int n,m;
UFS S;
Point ans=(Point){inf,inf};
Edge e[M];

//Kruskal,返回找到的点
inline Point Kruskal() {
    Point res=(Point){0,0}; int tot=0;
    sort(e+1,e+m+1,cmp); S.init(n);
    for (re int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,a=e[i].a,b=e[i].b;
        if (S.check(u,v)) continue;
        S.merge(u,v),res.x+=a,res.y+=b,++tot;
        if (tot==n-1) break;
    }
    /*更新答案*/
    ll Ans=1ll*ans.x*ans.y,now=1ll*res.x*res.y;
    if (Ans>now||(Ans==now&&ans.x>res.x)) ans=res;
    return res;
}

//递归处理
inline void solve(Point A,Point B) {
    for (re int i=1;i<=m;++i) e[i].w=e[i].b*(B.x-A.x)+e[i].a*(A.y-B.y);
    Point C=Kruskal();
    if (cross(B-A,C-A)>=0) return; //边界
    solve(A,C),solve(C,B);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i)
        e[i].u=read()+1,e[i].v=read()+1,e[i].a=read(),e[i].b=read();
    for (re int i=1;i<=m;++i) e[i].w=e[i].a;
    Point A=Kruskal();
    for (re int i=1;i<=m;++i) e[i].w=e[i].b;
    Point B=Kruskal();
    solve(A,B); printf("%d %d\n",ans.x,ans.y);
    return 0;
}