链接
题意
给 n ( 1 ≤ n ≤ 1 0 9 ) n(1 \leq n \leq 10^9) n(1≤n≤109) 个点的图，并给长度为 m ( 1 ≤ m ≤ 1 0 5 ) m(1 \leq m \leq 10^5) m(1≤m≤105) 的两个数组 a , b ( 1 ≤ a i ≤ n − 1 , 1 ≤ b i ≤ 1 0 9 ) a,b(1 \leq a_i \leq n - 1,1 \leq b_i \leq 10^9) a,b(1≤ai≤n−1,1≤bi≤109)。
每次可选择在点
x
(
1
≤
x
≤
n
)
x(1\leq x\leq n)
x(1≤x≤n) 和
(
x
+
a
i
)
m
o
d
n
(x + a_i)\mod n
(x+ai)modn 中添加一个长度为
b
i
b_i
bi 的边，问添加的边的长度总和至少为多少，才能使得整个图连通，不连通输出 -1。
思路
考虑
m
=
1
m = 1
m=1 时，如果要建成联通图，必须要让
gcd
(
n
,
a
1
)
=
1
\gcd(n,a_1) = 1
gcd(n,a1)=1，否则会发生如下情况：
如果
m
>
1
m > 1
m>1 则同理可得当
gcd
(
n
,
a
1
,
a
2
⋯
a
m
)
=
1
\gcd(n,a_1,a_2\cdots a_m) = 1
gcd(n,a1,a2⋯am)=1 时有解。这样我们已经解决了判断无解的情况。
对于任意一个 i i i，可知最多可将剩下的 p p p 个点合并成剩下 gcd ( p , a i ) \gcd(p,a_i) gcd(p,ai) 个点，我们先按照 b i b_i bi 大小排序，对于每一次操作连通块的数量都由 p ← gcd ( p , a i ) p \gets \gcd(p,a_i) p←gcd(p,ai)，则 a n s ← a n s + ( p − gcd ( p , a i ) ) × b i ans \gets ans + (p - \gcd(p,a_i)) \times b_i ans←ans+(p−gcd(p,ai))×bi。若有解，最后输出 a n s ans ans 即可。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int gcd(int x,int y) {
return y?gcd(y,x % y):x;
}
struct edge{
int a,b;
friend bool operator <(edge x,edge y) {
return x.b < y.b;
}
}node[200005];
int ans = 0;
signed main() {
cin >> n >> m;
for(int i = 1;i <= m;i++) cin >> node[i].a >> node[i].b;
sort(node + 1,node + m + 1);
for(int i = 1;i <= m;i++) {
ans += (n - gcd(n,node[i].a)) * node[i].b;
n = gcd(n,node[i].a);
if(n <= 1) {
cout<<ans<<endl;
return 0;
}
}
cout<<"-1"<<endl;
return 0;
}