ABC210E Ring MST 题解

题意：给定一张 $n$ 个点的无向图，顶点的编号为 $0,1,\dots,n−1$ 。同时给出两个长度为 $m$ 的数组 $a_1,a_2,\dots,a_m$ 和 $b_1,b_2,\dots,b_m$ 。初始时图中并没有任何边，你可以按照以下操作加边:

选择一个 $1\le i\le m$ 和一个 $0<x<n$ ，并在顶点 $x$ 和顶点 $(x+a_i) \bmod n$ 中添加一条长度为 $b_i$ 的边。

你现在想要知道，你添加的边的长度总和至少为多少，才能使得整个图连通?如果无论如何都不能使整个图连通，输出 $−1$ 。

数据范围：

$1 \le a_i < n \le 10^9,~1 \le m \le 10^5,1\le b_i \le 10^9$

首先我们可以想到把 $(x,(x+a_i)\bmod n)$ 看作一条边

然后答案就是最小生成树，跑个 $\text{kruskal}$

不过这个是 $O(nm)$ 的，这是不能接受的

于是我们模拟 $\text{kruskal}$ 的算法过程，不过更加快捷

把 $(a_i,b_i)$ 按 $b_i$ 排序升序排序，保证有 $\forall i < j,~b_i\le b_j$

然后考虑尽可能的用较前的 $(a_i,b_i)$ 来建边

有一个结论：令 $g=\gcd(a_i,n)$ ，

则所有模 $g$ 相同的结点均可以连到同一个连通块，并且会有 $g$ 个这样的连通块

注：此时我们尽可能在用 $a_i$ 建边，这里连到同一个连通块就是指尽可能建边的结果

这个结论其实证起来很简单

方便起见，我们固定 $0$ 为起点，显然这不会影响答案

则只用 $a_i$ 从 $0$ 可以走到的点一定是 \[ (a_ix+ny) \bmod n \] 其中 $x,y \in \mathbb{Z}$ 。

令 $c=a_ix+ny$ ，根据裴蜀定理可知，如果有解，则 $g \mid c$

注意我们这里是 $c$ ，实际上我们还会从 $0,1,\dots,g-1$ 出发去连边

不难发现这样我们会连出 $g$ 个这样的连通块

然后我们试着去推广这个结论

如果我们用前 $i$ 个 $a_i$ ，则他们一共有 $g=\gcd(a_1,a_2,\dots,a_i,n)$ 个连通块

详细证明我也不太会，但是这个就是个很显然的结论

不难发现，当 $g=1$ 时，图就联通了。

然后这题就没了。边权只要用 $\sum(g_{i-1}-g_{i}) \times b_{i}$ 来算就行啦

这题我在Roundgod老师的指导下想了一个小时左右才想明白 QAQ

时间复杂度 $O(m\log m)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define F first
#define S second
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
typedef pair<int,int> P;
int n,m;
vector<P> vec;
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; vec.clear();
    for(int i=1,u,v; i<=m; i++)
    {
        cin >> u >> v;
        vec.push_back({v,u});
    }
    sort(vec.begin(),vec.end());
    int ans=0,g=n;
    for(int i=0; i<m; i++)
    {
        int tmp=g;
        g=gcd(g,vec[i].S);
        ans+=(tmp-g)*vec[i].F;
    }
    if(g!=1) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}