CF1245D题解

· · 题解

与其他题解不同的做法。

首先我们按照题目要求，在 n 个点之间建好图。

回忆 kruskal 算法的过程，我们先将边从小到大排列，假设每个点是一个孤立的子集，若一条边连接 u 和 v，而所有边权小于这条边的边无法使这两个点连通，那么这条边就在最小生成树上。

本题与裸的最小生成树的不同之处就在与每个点有一个可以选择的权值。很容易想到，对于一个连通块，我们仅选择权值最小的那个点建造发电站是最优的。

因此考虑和 kruskal 相同的过程，我们先在每个点上都建一个发电站，将边从小到大排列后依次枚举，若将两个连通块连上，取权值最小点建造发电站比在两个连通块上分别建造连通块更优，则我们在这两点间连接电缆。

考虑什么情况下在两点间连接电缆更优。设边 (u,v) 的权值为 w_i，u 点所在连通块上权值最小值（唯一的建造发电站的点上取到）为 c'_u，同理得知 v 点对应的 c'_v，此时 u 和 v 还不连通。如果不在 u 和 v 间连接电缆，对答案的贡献显然为 c'_u+c'_v+\sum w（这里 \sum w 指的是两个连通块已连接边的权值之和）；如果连接，对答案的贡献就是 \min (c'_u,c'_v)+\sum w+w_i。

比较二者大小，当 c'_u+c'_v+\sum w\ge \min (c'_u,c'_v)+\sum w+w_i 时，化简得 \max (c'_u,c'_v) \ge w_i，此时在两点间连接电缆更优。反之不连接更优。

考虑代码实现，我们需要做一次正常的 kruskal，即因为图的最小生成树是不变的，我们要考虑的是在哪些点上建造发电站和选取哪些边连接电缆，不可能选取原来不在最小生成树上的边连接，原因根据最优性显然。所以我们另外开一个并查集记录当前连接电缆情况，在两点之间不用电缆连接更优时，我们也需要在最小生成树对应的并查集上合并两点所在集合，代表已经考虑过是否连接电缆，此时的 w_i 已经比 \max (c'_u,c'_v) 要大，往后枚举时 w_j\ge w_i，所以在两点所在的连通块上不可能连接电缆，所以无需考虑连接两个连通块的其他边。

时间复杂度为 O(n^2\log n^2)。

#include<bits/stdc++.h>
using namespace std;
int n,xi[2005],yi[2005],c[2005],k[2005];
struct edge{
    int u,v;
    long long w;
}e[4000005];
int fa[2005],link[2005];
int tot=0;
bool s[2005];
long long ans=0;
vector<pair<int,int> > v_edge;
bool cmp(edge x,edge y){return x.w<y.w;}
int find(int k){return (fa[k]==k)?k:fa[k]=find(fa[k]);}
int find_link(int k){return (link[k]==k)?k:link[k]=find(link[k]);}
void print(){
    cout<<ans<<"\n";
    int res=0;
    vector<int> v_res;
    for(int i=1;i<=n;i++) s[find_link(i)]=true;
    for(int i=1;i<=n;i++)
        if(s[i]) v_res.push_back(i),res++;
    cout<<res<<"\n";
    for(int i=0;i<res;i++) cout<<v_res[i]<<" ";
    cout<<"\n";
    cout<<n-res<<"\n";
    for(int i=0;i<n-res;i++) cout<<v_edge[i].first<<" "<<v_edge[i].second<<"\n";
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>xi[i]>>yi[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>k[i];
    for(int i=1;i<=n;i++){
        fa[i]=link[i]=i,ans+=1ll*c[i];
        for(int j=1;j<=n;j++)
            e[++tot].u=i,e[tot].v=j,e[tot].w=1ll*(k[i]+k[j])*(abs(xi[i]-xi[j])+abs(yi[i]-yi[j]));
    }
    sort(e+1,e+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        if(find(e[i].u)==find(e[i].v)) continue;
        int fu=find_link(e[i].u),fv=find_link(e[i].v);
        if(c[fu]<c[fv]) swap(fu,fv);
        if(c[fu]>=e[i].w){
            ans+=e[i].w-c[fu],link[fu]=fv;
            v_edge.push_back(make_pair(e[i].u,e[i].v));
        }
        fa[fu]=fv;
    }
    print();
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    /*int tt;cin>>tt;while(tt--)*/solve();
    return 0;
}