けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 210 E - Ring MST (青色, 500 点)

AtCoder AtCoder500点 青色diff ABC-E グラフ Kruskal法 最小全域木 数学(整数問題) 互いに素 最大公約数 ベズーの等式

また 1 つ、MST 系の問題のストックが増えた。でも実質的には整数問題だった。

問題概要

頂点数 N、辺数 0 のグラフがある。このグラフに以下の操作 1, 2, \dots, M を実施することで重み付き無向グラフを作る。

  • x = 0, 1, \dots, N-1 に対して、頂点 x と頂点 (x + A_{i}) % N の間に、重み C_{i} の辺を張る

こうしてできる辺数 NM のグラフにおいて、最小全域木の重みを求めよ。

制約

  • 2 \le N \le 10^{9}
  • 1 \le M \le 10^{5}

考えたこと

Kruskal 法をやるのには違いない。というわけで、 C_{i} の値が小さい順に処理していく。

このとき、たとえば A_{i} と N が互いに素ならば、もうコスト C_{i} の辺だけで MST が作れる。

一般には g = \mathrm{gcd}(N, A_{i}) としたとき、たとえ N 辺すべて結んだとしても、 g 個の連結成分に分かれることになる。

その後は実は、各連結成分を 1 頂点に潰してしまって、頂点番号が 0, 1, \dots, g-1 であるような頂点数 g のグラフに対して、問題文で示されたような辺が張られていくものと考えてもよいことが言える。

よって、次のコード例のように実装できる。

コード

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> A(M), C(M);
    for (int i = 0; i < M; ++i) cin >> A[i] >> C[i];
    
    vector<int> ids(M);
    for (int i = 0; i < M; ++i) ids[i] = i;
    sort(ids.begin(), ids.end(), [&](int i, int j){return C[i] < C[j];});
    
    long long res = 0;
    for (auto i : ids) {
        long long N2 = gcd(N, A[i]);
        res += (N - N2) * C[i];
        N = N2;
    }
    cout << (N == 1 ? res : -1) << endl;
}