CF1245D Shichikuji and Power Grid 题解

FlyPancake · 2024-01-07 15:56:53 · 个人记录

CF1245D Shichikuji and Power Grid 题解

Ideas

这道题核心思想就是用一个虚拟节点与每个点建边，边权为建造发电站的代价。具体过程其他 dalao 已经讲了。这里我给出一个 Kruskal 的解法。

考虑到这道题每两个节点之间都会有边，所以 Kruskal 算法的时间复杂度为 \mathcal{O}(N^2 \times \log_2 N^2)。虽然 Kruskal 比 prim 更劣，但是还是值得学习的。不会的可以先看看模板。（特地给的不是真的【模板】，因为 P1550 与该题更加接近，话说也没人会模板就没打就来打这题吧）

细节：

• 输出特别毒瘤。讨论区里有一个翻译。

• 记得开 long long！

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2005;

struct node{
    int u, v;
    ll w;
    friend bool operator <(node a, node b){
        return a.w<b.w;
    }
}e[MAXN*MAXN+MAXN], data[MAXN], con_num[MAXN];

int fa[MAXN], X[MAXN], Y[MAXN], k[MAXN], build_num[MAXN]; 
ll cnt, ans, tot, datatot;
int n, m;

int find(int x){
    if(x==fa[x]) return x;
    fa[x] = find(fa[x]);
    return fa[x];
}

void kruskal(){
    sort(e+1, e+tot+1);
    for(int i=1; i<=n; ++i){
        fa[i] = i;
    }
    for(int i=1; i<=tot && cnt<=n; i++){
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv){
            fa[fu] = fv;
            ans += e[i].w;
            data[++datatot].u = e[i].u, data[datatot].v = e[i].v;
            cnt++;
        }
    }
}

void print(){
    cout<<ans<<"\n";
    int build_cnt = 0, con_cnt = 0;
    for(int i=1; i<=datatot; i++){
        if(data[i].u==0) build_num[++build_cnt] = data[i].v;
        else con_num[++con_cnt].u = data[i].u, con_num[con_cnt].v = data[i].v;
    }
    cout<<build_cnt<<"\n";
    for(int i=1; i<=build_cnt; i++) cout<<build_num[i]<<" ";
    cout<<"\n"<<con_cnt<<"\n";
    for(int i=1; i<=con_cnt; i++) cout<<con_num[i].u<<" "<<con_num[i].v<<"\n"; 
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>X[i]>>Y[i];
    }
    for(int i=1; i<=n; i++){
        ll c; cin>>c;
        e[++tot].u = 0, e[tot].v = i, e[tot].w = c;  // 虚拟节点 
    }
    for(int i=1; i<=n; i++) cin>>k[i];
    for(int i=1; i<=n; 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(X[i]-X[j])+abs(Y[i]-Y[j])); // 建立两点相连的边 
        }
    }
    kruskal();
    print();
    return 0;
}