[JZOJ 5888] [NOIP2018模拟9.29] GCD生成树 解题报告 （最大生成树+公约数）

题目链接：

http://172.16.0.132/senior/#main/show/5888

题目：

题解：

思路是这样的：两个数的最大公约数一定不会比这两个数的任意一个数大。因此我们把权值相等的看成一个点，先把这些点连起来算上贡献

考虑kruskal的做法，我们从大到小枚举边权，其实就是我们从大到小枚举最大公约数。假设当前枚举到i，我们再枚举$k_1$,$k_2$，判断$k_1i$,$k_2i$是否存在，若是存在再判断二者是否连通，如果没有连通就连起来算上i的贡献。或许有的人会想这样$2i$,$4i$的贡献不就算小了吗？注意我们是从大到小枚举，这样的情况在枚举$2i$的时候就已经连边了

但是这样枚举两个$k$会T掉，怎么处理呢？实际上我就是要把这些倍数都放到一个连通块里，于是每次枚举到一个i的时候我们把所有$i$的倍数的点连向一个钦定的点（这个点就设为第一个$i$的倍数的点），这样我们就只需要枚举一个$k$就好了,不管是哪个合并到哪个，贡献都会是$i$

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

const int N=1e5+;

int n,mx,cnt,pnt;

ll ans;

int a[N],vis[N],fa[N];

inline int read(){

    char ch=getchar();int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

void chkmax(int &x,int y) {if (y>x) x=y;}

int find(int x) {if (fa[x]!=x) fa[x]=find(fa[x]);return fa[x];}

int main()

{

    freopen("gcd.in","r",stdin);

    freopen("gcd.out","w",stdout);

    n=read();

    for (int i=,x;i<=n;i++) {

        x=read();if (vis[x]) {ans+=x;continue;}

        vis[x]=;fa[x]=x;

        a[++cnt]=x;chkmax(mx,x);

    }

    for (int i=mx;i&&pnt<cnt-;i--)

    {

        int x=,y;

        for (int k=,p;k*i<=mx&&pnt<cnt-;k++){

            if (!vis[p=k*i]) continue;

            y=find(p);

            if (!x) x=y;else if (y!=x) fa[y]=x,ans+=i,++pnt;

        }

    }

    printf("%lld\n",ans);

    return ;

}