题目链接
题目解法
不是,我这咋不会做/fn
边数很多的最小生成树有一个方法是 \(boruvka\),但这个处理完全图的比较方便
另一个方法是用到一个 \(trick\):连出的图中的环,可以删去最长边
扫描线是容易想到的,主要是如何把连的边数缩减到合理的范围内
考虑扫描线到当前时刻时,我们已经维护出了这个时刻存在的区间
给出结论:加点 \(x\) 时,我们只需要 \(x\) 连到当前时刻存在的比 \(v_x\) 恰好大的和恰好小的点
证明手画一画就可以了
最后连出的边数是 \(O(n)\) 的,直接求 \(mst\) 即可
时间复杂度 \(O(n\log n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=500010;
int l[N],r[N],v[N],disc[N<<1];
vector<int> ins[N<<1],del[N<<1];
#define fi first
#define se second
set<pii> se;
typedef tuple<int,int,int> tup;
tup edge[N<<1];
int fa[N];
int gfa(int x){ return x==fa[x]?x:fa[x]=gfa(fa[x]);}
void work(){
int n;read(n);
F(i,1,n) read(l[i]),read(r[i]),read(v[i]);
int cnt=0;
F(i,1,n) disc[++cnt]=l[i],disc[++cnt]=r[i];
sort(disc+1,disc+cnt+1);
cnt=unique(disc+1,disc+cnt+1)-disc-1;
F(i,1,n){
l[i]=lower_bound(disc+1,disc+cnt+1,l[i])-disc;
r[i]=lower_bound(disc+1,disc+cnt+1,r[i])-disc;
ins[l[i]].pb(i),del[r[i]+1].pb(i);
}
int tote=0;
F(i,1,cnt+1){
for(int id:del[i]) se.erase({v[id],id});
for(int id:ins[i]){
if(!se.empty()){
auto itr=se.lower_bound({v[id],id});
if(itr!=se.end()) edge[++tote]={(itr->fi)-v[id],id,itr->se};
if(itr!=se.begin()){
auto itl=prev(itr);
edge[++tote]={v[id]-(itl->fi),id,itl->se};
}
}
se.insert({v[id],id});
}
}
sort(edge+1,edge+tote+1);
F(i,1,n) fa[i]=i;
LL ans=0;int con=0;
F(i,1,tote){
auto [z,x,y]=edge[i];x=gfa(x),y=gfa(y);
if(x!=y) ans+=z,fa[x]=y,con++;
}
if(con==n-1) printf("%lld\n",ans);else puts("-1");
F(i,1,cnt+1) ins[i].clear(),del[i].clear();
}
int main(){
int T;read(T);
while(T--) work();
return 0;
}
标签:Turtle,ch,int,题解,Segments,edge,id,se,define
From: https://www.cnblogs.com/Farmer-djx/p/18226413