首页 题解 杂

题面:
P 国的国土可以描述为有一张 nn 个点 mm 条的无向图，其中每个点表示 P 国的一座城市，编号为 1,2,…,n1,2,\dots,n，每条边表示 P 国的一条道路，编号为 1,2,…,m1,2,\dots,m。

P 国的每条道路都有一个宽度 wiw_i，而一辆宽度为 xx 的车能从城市 ii 走到城市 jj 当且仅当存在一条从 ii 到 jj 的路径使得路径上所有边的宽度都 ≥w\ge w。

现在 P 国可能会有一些车辆无法从某个城市到达另一个，这时这些车辆便会投诉国王小 P，所以小 P 需要尽快多修建一些道路使得他能尽可能满足车辆的需求。

具体的，给定一个长度为 nn 的序列 a1,a2,…,ana_1,a_2,\dots,a_n，小 P 可以在在城市 i,ji,j 之间花费 ai+aja_i+a_j 元修建超级道路，超级道路的宽度是无限的。

现在有 qq 次询问，每次给定一个 xx，请你帮助国王小 P 求出至少花费多少元用来修建道路才能使得宽度为 xx 的车能从任意一个点走到任意另一个点。

1≤n,m,q≤3×105,0≤wi,x,ai≤1091\leq n,m,q \leq 3\times 10^5,0\leq w_i,x,a_i\leq 10^9

解法：
这个题跟 USACO18JAN MooTube G 是很像的，我们也可以那么做，即把询问沿宽度从大到小排序，给的边也根据从大到小进行排序，以询问的权值为下限，不断加入边。

那么我们考虑怎么算出贡献。发现根据连边，最后肯定是形成多个（也有可能是一个）连通块，既然每天道路所需的费用为 ai+aja_i+a_j 那么我们就让每个连通块中的最便宜的进行连接，注意这里不是互相连接，只需要联通即可，所以最优肯定是让所有联通块中所需代价最小的点，去连接别的连通块中代价最小的点。

记 sumsum 为每个点的 aia_i 之和，每次连通块合并就让减去连通块最小值较大的，合并后的连通块是合并前最小值较小的那个，这样剩下的 sumsum 就是每个连通块最小值的和，那么全局最小值 (minxminx) 需要 cnt−1cnt-1 次（cntcnt 为连通块个数） ，在 sumsum 中还包含一次，所以总的代价为 sum+(cnt−1)×minxsum+(cnt-1) \times minx

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <iomanip>
#include <climits>
#define int long long
using namespace std;
const int MAXN=1e6+10;
struct edge{
    int nex,to,val;
}p[MAXN];
struct node{
    int val,fla;
}quebox[MAXN];
int head[MAXN],cnt,minx=INT_MAX,fa[MAXN],minn[MAXN],siz[MAXN];
int a[MAXN],ans,anss[MAXN];
bool cmp(edge x,edge y){
    return x.val>y.val;
}
bool cmp2(node x,node y){
    return x.val>y.val;
}
int find(int x){
    if(x==fa[x]){
        return fa[x];
    }
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx==fy){
        return;
    }
    if(siz[fx]>siz[fy]){
        swap(fx,fy);
    }
    fa[fx]=fy;
    if(minn[fx]>minn[fy]){
        ans-=minn[fx];
    }else{
        ans-=minn[fy];
    }
    minn[fy]=min(minn[fx],minn[fy]);
    cnt--;
}
signed main(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        minx=min(minx,a[i]);
        ans+=a[i];
        siz[i]=1;
        fa[i]=i;
        minn[i]=a[i];
        cnt++;
    }
    for(int i=1;i<=m;i++){
        cin>>p[i].nex>>p[i].to>>p[i].val;
    }
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=q;i++){
        cin>>quebox[i].val;
        quebox[i].fla=i;
    }
    sort(quebox+1,quebox+q+1,cmp2);
    int now=0;
    for(int i=1;i<=q;i++){
        for(int j=now+1;j<=m;j++){
            if(p[j].val<quebox[i].val){
                now=j-1;
                break;
            }
            merge(p[j].nex,p[j].to);
        }
        if(cnt==1){
            anss[quebox[i].fla]=0;
        }else{
            anss[quebox[i].fla]=ans+(cnt-2)*minx;
        }
        
    }
    for(int i=1;i<=q;i++){
        cout<<anss[i]<<endl;
    }
}