代码

#include <iostream>
#include <bits/stdc++.h>
#define maxn 300010
using namespace std;
int n,m,qn,f[maxn],x,y,z,k,fv[maxn],ma[maxn],bo;
struct sx{
    int x,k,ans;
}q[maxn];
struct ubt{
    int x,y,z;
}test[maxn];
vector <int> qs[maxn];
int found(int x){
    if(f[x]==x)return x;
    return f[x]=found(f[x]);
}
bool acmp(sx a,sx b){
    return a.x<b.x;
}
bool bcmp(sx a,sx b){
    return a.k<b.k;
}
int main(){
    cin>>n>>m>>qn;
    for(int i=1;i<=n;i++)cin>>k,bo+=k,ma[i]+=k;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>test[i].x>>test[i].y>>test[i].z;
    }
    for(int i=1;i<=qn;i++){
        cin>>q[i].x;q[i].k=i;
    }
    sort(q+1,q+1+qn,acmp);
    for(int i=1;i<=qn;i++){
        for(int j=1;j<=m;j++){
            if(test[j].z<q[i].x&&test[j].z>=q[i-1].x){
                fv[j]=1;qs[i].push_back(j);
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(!fv[i]){
            int x=found(test[i].x);
            int y=found(test[i].y);
            f[y]=x;ma[x]=min(ma[x],ma[y]);
         //   cout<<test[i].x<<" "<<test[i].y<<" "<<x<<" "<<y<<"\n";
         //   for(int i=1;i<=n;i++)cout<<f[i]<<" ";
        }
      // cout<<"\n";
    }
    for(int i=qn;i>=1;i--){
        memset(fv,0,sizeof(fv));
        int e=2147483647,cnt=0,sum=0;
        for(int j=1;j<=n;j++){
            int x=found(j);
            if(!fv[f[x]])fv[f[x]]=1,e=min(e,ma[f[x]]),cnt++,sum+=ma[f[x]];
        }
        q[i].ans=(cnt-2)*e+sum;
     //   cout<<ans[i]<<" "<<cnt<<" "<<e<<" "<<sum<<" "<<"\n";
        for(int j=0;j<qs[i].size();j++){
            int k=qs[i][j];
            int x=found(test[k].x),y=found(test[k].y);
            f[y]=x;ma[x]=min(ma[x],ma[y]);
        }
    }
    sort(q+1,q+1+qn,bcmp);
    for(int i=1;i<=qn;i++)cout<<q[i].ans<<"\n";
    return 0;
}

评测结果