CF2081D MST in Modulo Graph

Tag：MST、并查集、数论

题目描述

给定一个包含 \(n\) 个顶点的完全图，其中第 \(i\) 个顶点的权值为 \(p_i\)。连接顶点 \(x\) 和顶点 \(y\) 的边的权重等于 \(\operatorname{max}(p_x, p_y) \bmod \operatorname{min}(p_x, p_y)\)。

请找出连接图中所有 \(n\) 个顶点的 \(n - 1\) 条边组成的集合的最小总权重。

数据说明：

\(1 \le t \le 10^4\)

\(1 \le n \le 5 \cdot 10^5\)

\(1 \le p_i \le 5 \cdot 10^5\)

\(\sum n \leq 5 \cdot 10^5\)

\(\max(p_1,p_2,\ldots,p_n) \leq 5 \cdot 10^5\)

分析

首先要从 \(\operatorname{max}(p_x, p_y) \bmod \operatorname{min}(p_x, p_y)\) 这个式子开始观察，对于两个点权相同的点来说，我们可以无代价连上这条边，不妨直接把相等的点看做一个点。我们进一步观察式子，因为我们算的是大数模小数，所以如果两个数字呈倍数关系，那么也可以无代价连这条边，上面所说的点权相等其实就是一种倍数为 \(1\) 的情况。

上述的连边都是无代价的连边，我们实际上最需要考虑的是如何把非倍数关系的点进行连接。

我们考虑一下这种情况，比如现在的点权分别为 \(\{2,4,5\}\)，其中的 \(2\) 和 \(4\) 呈现出倍数关系，对于 \(5\) 来说，连谁都是等价的，代价都为 \(1\)。那么我们再看一组 \(\{2,4,7\}\)，在这一组中，用 \(7\) 和 \(2\) 连明显是更优的，于是我们可以得出一个结论：如果同时存在 \(x\) 和 \(kx\)，选择和 \(x\) 连接一定是不劣的。我们和 \(kx\) 连边时，有可能会付出大于 \(x\) 的代价，但是和 \(x\) 连边的代价一定小于 \(x\)。

我们下一步就考虑 \(x\) 的倍数，假设我们在 \([kx,(k+1)x]\) 这个区间中，存在 \(y\) 与 \(z\) 两个数，满足 \(kx \leq y < z \leq (k+1)x\)。那么我们考虑一下怎么连，不难发现两种方案，一个是 \((kx,y)\) 和 \((y,z)\)，另一种是 \((kx,y)\) 和 \((kx,z)\)。观察上述方案，我们可以发现其代价分别为 \((y - kx) + (z - y)\) 与 \((y - kx) + (z - kx)\)。明显前者不劣于后者，因此我们会选择连接 \((kx,y)\)，不过由于我们之前说的连接 \(x\) 不劣于连接 \(kx\)。所以实际上我们选择连接的是 \((x,y)\)。

于是产生了这样一种思路，我们从小到大枚举所有的点的倍数区间，在每一个区间里面我们都只连第一个点，把这条边选出来备用。区间里剩下的点，会在后续遍历到这个点的时候为他连一条边。这样的复杂度是一个调和级数，也就是说我们一共能找到 \(nlogn\) 条边，其中的 \(n\) 为点权不同的点的个数。并且我们如果把这 \(nlogn\) 条边全部连接，最后的图一定是连通的，因为我们遍历过程中，对于每一个点都至少选择了一条边向外链接。

在我们得到了所有的边之后，从代价从小到大遍历这些边，使用 \(\text{DSU}\) 维护连通性，复杂度为 \(O(n logn \cdot \alpha(n))\)。

代码实现

struct DSU{
public:
    static const int MAX = 5e5 +5;
    int bcj[MAX];
    int siz[MAX];
    void Init(int n){
        for (int i = 1; i <= n; ++i) bcj[i] = i,siz[i] = 1;
    }
    int Find(int x){
        if(bcj[x] == x) return x;
        return bcj[x] = Find(bcj[x]);
    }
    //按秩合并
    void Union(int x,int y){
        x = Find(x),y = Find(y);
        if(x == y) return;
        if(siz[x] > siz[y]) swap(x,y);
        bcj[x] = y,siz[y] += siz[x];
    }
//普通合并
//void Union(int x, int y){
//    bcj[Find(x)] = Find(y);
//}
};
DSU dsu;
void NeverSayNever() {
    int n; cin >> n;
    vector<int> vec(n);
    for (auto &x: vec) cin >> x;
    int mx = *std::max_element(vec.begin(), vec.end()) + 2;
    vector<int> nxt(mx);
    nxt.back() = 2 * mx;
    for (auto &x: vec) nxt[x] = x;
    for (int i = mx - 2; i > 0; --i) {
        if (nxt[i] == 0) nxt[i] = nxt[i + 1];
    }
    //edge[i] 表示选取代价为 i 的边集
    vector<vector<PII>> edge(mx);
    std::sort(vec.begin(), vec.end());
    vec.resize(n = unique(vec.begin(), vec.end()) - vec.begin());
    for (int i = 0; i < n; ++i) {
        if (i < n - 1) {
            edge[vec[i + 1] % vec[i]].push_back({vec[i], vec[i + 1]});
            for (int j = 2 * vec[i]; j < mx; j += vec[i]) {
                if (nxt[j] < j + vec[i]) {
                    edge[nxt[j] - j].push_back({vec[i], nxt[j]});
                }
            }
        }
    }
    dsu.Init(mx + 5);
    int ans = 0;
    for (int i = 0; i < mx; ++i) {
        for (auto &[u, v]: edge[i]) {
            if (dsu.Find(u) != dsu.Find(v)) {
                ans += i;
                dsu.Union(u, v);
            }
        }
    }
    cout << ans << endl;
}

日志

本页面创建于 2025/03/20 11:35