题解：P14548 [IO 2024 #3] 拯救波利尼西亚

· · 题解

思路流程

首先这明显是一个生成树的过程，回忆 kruskal 的过程，我们先将 k 个新岛按 c 从小到大排序。
然后发现对于每个 i 只有对 [l,r] 中所有联通快连一条边就行。
这个东西好维护的，线段树、ODT、还有并查集都行，这里采用并查集实现。
均摊时间复杂度：O(k\log k+k\alpha(n))。

代码实现

#include<bits/stdc++.h>
using namespace std;
Code by MKS;
#define debug(i) cout<<"Cute_MKS "<<i<<' '
#define int long long
const int N=5e5+10;
int n,m,ans,prt[N];
struct Que
{
    int l,r,c;
    bool operator<(const Que &x){return c<x.c;}
}q[N];
int find(int p){return p==prt[p]?p:prt[p]=find(prt[p]);}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r>>q[i].c;
    for(int i=1;i<=n;i++) prt[i]=i; 
    sort(q+1,q+m+1);
    for(int i=1;i<=m;i++)
    {
        int l=q[i].l,r=q[i].r,c=q[i].c,p=l,sum=0;
        vector<int>v;
        while(1)
        {
            p=find(p);sum++;
            if(p>=r) break;
            v.push_back(p);
            p++;
        }
        for(int i=0;i<v.size();i++) prt[v[i]]=p;
        ans+=sum*c;
    }
    if(find(1)!=n)
    {
        cout<<-1;
        return 0;
    }
    cout<<ans;
}