Sirni

发表于 |
字数统计: 510 | 阅读时长 ≈ 2
  • Code Level: ※※
  • Thinking Level: ※※

Description

有 n 个点，每个点有个权值 p1, p2,…,pn。这些点之间两两有边，对于点 i, j，这两个点之间的边权为

问把这些点连通的最小代价和是多少，也就是问这个完全图的最小生成树的边权和。

Solution

对于生成图，一看数据n方过百万，就知道要用玄妙的方法来构成边去跑克鲁斯卡尔了

观察边权的表达式，可以知道存在多余的权值相等的点是无意义的（连接耗费为零），所以可以先去重

再一次观察发现对于mod k的答案，在每一个段（段长k）中是有序的。即

所以根据此加边即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int nn=1e5+5;;
const int mn=1e7+5;
int n,p[nn],d[nn],f[nn],mr[mn*2],pos[2*mn],tot=0;bool vis[nn];long long ans=0;
struct dat{
    int from,to,cost;
    friend bool operator<(dat a,dat b){
        return a.cost<b.cost;
    }
}e[nn*405];
int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}
int main(){
    int i,j,x,y,cnt=0; long long ans=0;
    scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&p[i]);
    sort(p+1,p+1+n); n=unique(p+1,p+1+n)-p-1;
    for(i=1;i<=n;i++) mr[p[i]]=p[i],pos[p[i]]=i;
    for(i=mn-2;i>0;i--) if(!mr[i]) mr[i]=mr[i+1],pos[i]=pos[i+1];
    for(i=1;i<n;i++){
        e[++tot]=(dat){i,i+1,p[i+1]%p[i]};
        for(j=p[i]*2;j<mn;j+=p[i]){
            if(!mr[j]) break;
            if(mr[j]>=j+p[i]) continue ;
            e[++tot]=(dat){i,pos[mr[j]],mr[j]%p[i]};
        }
    } sort(e+1,e+1+tot);
    for(i=1;i<=n;i++) f[i]=i;
    for(i=1;i<=tot;i++){
        x=find(e[i].from);y=find(e[i].to);
        
        if(x==y) continue ;
        f[x]=y; ans+=e[i].cost; cnt++;
        if(cnt==n-1) break;
    }
    cout<<ans<<endl;
    return 0;
}