题目传送门
Step 1 理解题意
- 给定一张 n n n 个点的图，最开始时图中一条边都没有；
- 给出两个长度为 m m m 的数组 a , b a,b a,b
- 你可以按照以下操作加边：选择一个 i i i ( 1 ≤ i ≤ m 1 \le i \le m 1≤i≤m)和一个 x x x ( 0 ≤ x ≤ n 0 \le x \le n 0≤x≤n)，并在顶点 x x x 和顶点 ( x + a i ) m o d n (x + a_i) \bmod n (x+ai)modn中添加一条长度为 b i b_i bi 的边。
- 求添加的边的总和最小值使得图能联通如果无论如何都不能使整个图连通，输出 − 1 -1 −1。
Step 2 做法简介
对这道题的情况，我们可以进行分类讨论：
- 当
m
=
1
m = 1
m=1 此时当且仅当
g
c
d
(
a
1
，
n
)
=
1
gcd(a_1，n) = 1
gcd(a1，n)=1 是存在连通图，否则输出
−
1
-1
−1
2.当
m
>
1
m > 1
m>1 时，同理，应当使
g
c
d
(
a
1
,
a
2
,
.
.
.
,
a
m
,
n
)
=
1
gcd(a_1,a_2,...,a_m,n) = 1
gcd(a1,a2,...,am,n)=1时才存在连通图，其他情况均为无解。
对于有解的情况，对于任意一个
a
i
a_i
ai ，我们可以将剩下的
k
k
k 合并为
g
c
d
(
a
i
,
k
)
gcd(a_i,k)
gcd(ai,k)个点，且代价为
g
c
d
(
a
i
,
n
)
×
b
i
gcd(a_i,n) \times b_i
gcd(ai,n)×bi
所以，我们就可以用贪心解决这道题
首先先将
a
,
b
a,b
a,b 的结构体按照
b
b
b 的大小进行排序
然后从
1
1
1 到
m
m
m 选取
a
i
a_i
ai 并将
n
n
n 赋值为
n
←
g
c
d
(
a
i
,
n
)
n \gets gcd(a_i,n)
n←gcd(ai,n) ,
a
n
s
←
a
n
s
+
(
n
−
g
c
d
(
a
i
,
n
)
×
b
i
)
ans \gets ans + (n - gcd(a_i,n) \times b_i)
ans←ans+(n−gcd(ai,n)×bi)
直到
n
=
1
n = 1
n=1 时退出循环，并输出答案
a
n
s
ans
ans。
step 3 Ac code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int ans = 0;
struct node{
int a,b;
}tree[100005];
int cmp(node x, node y){
return x.b < y.b;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i = 1;i <= m; i++)
scanf("%lld%lld",&tree[i].a,&tree[i].b);
sort(tree+1, tree + 1 + m ,cmp);
for(int i = 1; i <= m ;i++){
ans += (n - __gcd(n, tree[i].a)) * tree[i].b;//代价
n = __gcd(n,tree[i].a);
if(n == 1) break;
}
if(n > 1) printf("-1");//无解
else printf("%lld",ans);
return 0;
}