P9488 题解

fuqingchen · 2023-07-30 19:58:10 · 题解

原题链接

P9488 ZHY 的生成树

题目简述

ZHY 有一个 n 个点的完全图，点 u 与点 v 的距离为 \gcd(u,v)，求这个完全图的最大生成树的边权之和。

解题思路

30 pts

直接暴力建图，跑一遍 kruskal。 不会 kruskal 的点这里。

60 pts

这时候你离正解已经很近啦！

首先考虑 n \le 10^6。n^2 建图纯属浪费（因为只有 n-1 条边是有用的），我们可以先枚举这条边的边权，然后由 i 向 i 的倍数进行连边，就可以拿到 60 pts 了。

100 pts

在 60 pts 上优化，主要的重复在于枚举倍数时重复了。为了尽量减少这种情况，在枚举时可以只枚举倍数为质数的情况，稍微卡一卡就能过了。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e7 + 10;
int n, m, fa[N], tot;
int prime[6000100], q, x, k;
bool isp[N];
void Prime() {
    for (register int i = 2; i <= 10000000; ++i) {
        if (isp[i] == 0) prime[++k] = i;
        for (register int j = 1; j <= k && i * prime[j] <= 10000000; ++j) {
            isp[i * prime[j]] = 1;
            if (!(i % prime[j])) break;
        }
    }
}
int find(int x) {
    if(x == fa[x]) return x;
    else return fa[x] = find(fa[x]);
}
void kruskal() {
    int cnt = 0;
    long long sum = 0;
    for(register int i = n / 2; i >= 1; --i) {
        int len = n / i;
        for (int u = 1; prime[u] * i <= n; ++u) {
            int x = find(i), y = find(prime[u] * i);
            ++tot;
            if (x != y) {
                ++cnt;
                sum += i;
                fa[y] = x;
                if (cnt == n - 1) {
                    cout << sum;
                    return;
                }
            }
        }
    }
}
signed main() {
    cin >> n;
    Prime();
    for (int i = 1; i <= n; ++i) fa[i] = i;
    kruskal();
    return 0;
}