题解：AT_abc210_e [ABC210E] Ring MST

· · 题解

题目大意

在一个有 n 个点的环形图中，给定 m 种加边操作。每种操作允许你在顶点 x 与 (x + a_i) \bmod n 之间连一条权值为 b_i 的边。求使图连通的最小代价。

思路

为了使总代价最小我们要选择先使用权值较小的操作。将所有操作按 b_i 升序排序，依次尝试合并。

根据循环群性质，从 0 出发经过的所有点都是 a_i 在模 n 意义下的倍数。这些点构成的集合大小是 \frac{n}{\gcd(n, a_i)}，整个图会被分成 g = \gcd(n, a_i) 个连通块。
同理，如果当前图中已有 g 个连通块，加入步长为 a_i 的边后连通块数量就会变为 g' = \gcd(g, a_i)。

每减少一个连通块就要消耗一条边。如果从 g 个连通块减到 g' 个就需要添加 g - g' 条边。产生的代价为：(g - g') \times b_i。

C++代码


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll a,ll b){
  if(b)return f(b,a%b);
  else return a;
struct E{ll a,b;};
bool c(E x,E y){return x.b<y.b;}

int main(){
    ll n,m,s=0;
    cin>>n>>m;
    vector<E> v(m);
    for(int i=0;i<m;i++)cin>>v[i].a>>v[i].b;
    sort(v.begin(),v.end(),c);
    ll g=n;
    for(int i=0;i<m;i++){
        ll t=f(g,v[i].a);
        if(t<g){
            s+=(g-t)*v[i].b;
            g=t;
        }
        if(g==1)break;
    }
    if(g==1)cout<<s;
    else cout<<-1;
    return 0;
}