full solution (a math problem)
The Borůvka algorithm is essentially a multiplexed Prim minimum spanning tree with complexity\(m\log n\)but inferior to Kruskal's\(\log\)
The algorithm flow looks like this
Consider the current graph (unconnected edges), which must consist of a number of connected blocks, and we consider connecting connected blocks
It can be thought that for any connected block, it should definitely be connected to the best possible connected block, and, if that connected block is not connected in this operation, no matter how later operations change the state of other connected blocks, the connected block is always monotonically non-decreasing, and the cost must be monotonically non-decreasing as well, so it is sufficient to directly connect it in this operation
Based on the above principle, one can try to enumerate all edges and then try to update the connected block where the endpoints are located with this edge, and for the connected block, an optimal edge is chosen to update itself
It is conceivable that in a single operation, there is always at least half of the connected blocks that are connected and disappear, with the complexity\(m\log n\)
Some of the points to note are as follows
- "Optimal edges" must be strict here, i.e. you need to ensure that there are no\(i,j\in [1,m]\)such that the two sides\(e_i=e_j\), as to why this is necessary, a classic example is heavy edging, if there is now\((1,2,w=1)\) cap (a poem)\((2,1,w=1)\) Two edges, which make the connecting block\(1\) and connecting block\(2\) can all be updated so that rings will be connected during the merge, ensuring strict optimality generally using numbering as a second keyword
- Of course, you can run a minimum spanning tree on an undirected graph, and the solution is to judge before you merge the connected blocks in the second loop.
Borůvka has a lot to judge, so be careful not to miss it!
P3366 [Template] Minimum Spanning Tree
#include<bits/stdc++.h>
using namespace std;
int n,m;
int best[100001];
struct edge{
int from,to,w;
int id;
bool used;
bool operator <(const edge&A)const{
if(w==) return id<;
return w<;
}
};
vector<edge>e={{0,0,0,0,true}};
struct dsu{
int fa[100001];
void clear(){
for(int i=1;i<=n;++i){
fa[i]=i;
}
}
int find(int id){
if(id==fa[id]) return id;
return fa[id]=find(fa[id]);
}
bool samefa(int x,int y){
int fx=find(x),fy=find(y);
return fx==fy;
}
bool join(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return false;
fa[fx]=fy;
return true;
}
}d;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;++i){
int x,y,z;
cin>>x>>y>>z;
e.push_back({x,y,z,i,false});
}
();
int ans=0,tot=0;
while(1){
bool flag=false;
memset(best,0,sizeof best);
for(edge i:e){
if( or (,)) continue;
int tmp=();
int tmp2=();
if(best[tmp]==0 or i<e[best[tmp]]){
best[tmp]=;
}
if(best[tmp2]==0 or i<e[best[tmp2]]){
best[tmp2]=;
}
}
for(int i=1;i<=n;++i){
if((i)==i){
if(best[i]!=0 and e[best[i]].used==false){
e[best[i]].used=true;
ans+=e[best[i]].w;
tot++;
(e[best[i]].from,e[best[i]].to);
flag=true;
}
}
}
if(!flag) break;
}
if(tot!=n-1) cout<<"orz";
else cout<<ans;
}
utilization
It is clear that Borůvka does not perform as well as Prim on dense graphs and Kruskal on sparse graphs
Then what's the point of having it?
This is because Borůvka applies to a special class of topics
This type of question is like Given a complete graph, the edge weights on the complete graph can be derived from the point weights of the endpoints by some kind of computation, find the minimum spanning tree
Such a question makes full use of the fact that Borůvka only merges\(\log n\) times in nature, something the other two minimum spanning tree algorithms cannot do
But that doesn't mean that you can just apply the template, violent Borůvka still in the\(n^2\log\) level, some graph with properties is needed to optimize the algorithm (generally to find the minimum edge weight quickly)
Starfleet (USSR)
Each point on the full graph has a point weight.\(a_i\)Definition\((u,v)(u\lt v)\) The edge weights of the\(a_v-a_u\)Minimum Spanning Tree
(probably green-blue)
We need to find the smallest edge of this point outward into another connected block in each round. Notice that when\(i\) When fixed, the minimum edge is either the prefix\([1, i)\) is taken at the maximum value of either\((i, n]\) The minimum value of the suffix inside is taken. We only need to maintain the maximum value for each prefix, and the maximum value that is not in the same connectivity block as the maximum value, and the same for the suffixes, to quickly find the minimum edge outward from that connectivity block
The time complexity is\(O(n \log n)\)
#include<bits/stdc++.h>
using namespace std;
const long long inf=0x3f3f3f3f3f3f3f3f;
int n;
int a[300005];
struct val_t{
long long val,pos;
inline bool operator<(const val_t&A)const{
return val<;
}
inline bool operator>(const val_t&A)const{
return val>;
}
inline bool operator!=(const val_t&A)const{
return pos!=;
}
};
inline val_t max(val_t a,val_t b){
return a>b?a:b;
}
inline val_t min(val_t a,val_t b){
return a<b?a:b;
}
struct pairval_t{
val_t x,y;
};
const val_t pos_inf={inf,0};
const val_t neg_inf={-inf,0};
inline pairval_t max(pairval_t a,pairval_t b){
pairval_t ans={max(,),neg_inf};
if(!= and >) =;
if(!= and >) =;
if(!= and >) =;
if(!= and >) =;
return ans;
}
inline pairval_t min(pairval_t a,pairval_t b){
pairval_t ans={min(,),pos_inf};
if(!= and <) =;
if(!= and <) =;
if(!= and <) =;
if(!= and <) =;
return ans;
}
struct pairval_t maxn[300001],minn[300001];
struct val_t val[300001];
inline val_t askmax(int x,int pos){
return (maxn[x].==pos)?maxn[x].y:maxn[x].x;
}
inline val_t askmin(int x,int pos){
return (minn[x].==pos)?minn[x].y:minn[x].x;
}
struct dsu{
int fa[300001];
inline void clear(){
for(int i=1;i<=n;++i){
fa[i]=i;
}
}
int operator[](int id){
if(id==fa[id]) return id;
return fa[id]=this->operator[](fa[id]);
}
}d;
inline long long Roukusaka(){
long long ans=0;
();
for(int i=1;i<=n;++i){
maxn[i].x={a[i],i};
maxn[i].y=neg_inf;
minn[i].x={a[i],i};
minn[i].y=pos_inf;
}
for(int i=2;i<=n;++i){
maxn[i]=max(maxn[i-1],maxn[i]);
}
for(int i=n-1;i>=1;--i){
minn[i]=min(minn[i+1],minn[i]);
}
while(1){
bool flag=false;
for(int i=1;i<=n;++i){
val[i]=pos_inf;
}
for(int i=1;i<=n;++i){
int now=d[i];
val_t p=askmin(i,now);
val_t q=askmax(i,now);
if(!=-inf and a[i]-<=val[now].val){
val[now]={a[i]-,};
}
if(!=inf and -a[i]<=val[now].val){
val[now]={-a[i],};
}
}
for(int i=1;i<=n;++i){
if(d[i]==i){
if(d[val[i].pos]==i or val[i].val==inf) continue;
[d[val[i].pos]]=i;
ans+=val[i].val;
flag=true;
}
}
for(int i=1;i<=n;++i){
maxn[i].x={a[i],d[i]};
maxn[i].y=neg_inf;
minn[i].x={a[i],d[i]};
minn[i].y=pos_inf;
}
for(int i=2;i<=n;++i){
maxn[i]=max(maxn[i-1],maxn[i]);
}
for(int i=n-1;i>=1;--i){
minn[i]=min(minn[i+1],minn[i]);
}
if(!flag) break;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
cout<<Roukusaka();
}
CF888G Xor-MST
Each point on the full graph has a point weight.\(a_i\)Definition\((u,v)(u\neq v)\) The edge weights of the\(a_u \operatorname{xor} a_v\)Minimum Spanning Tree
Consider putting into a trie tree to maintain dissimilarities and maxima
The yardage is okay, find some time to code
(purple)
seek
Given two weighted undirected trees\(T_1,T_2\)Definition\(dis_i(x,y)\) represent a tree\(T_i\) first (of multiple parts)\(x,y\) distance between them, there exists a completely bipartite graph with a left part, a right part with a\(n\) points, defining the left point\(i\) with the right point\(j\) The edge weights between\(\max\limits_{x=1}^n(dis_1(i,x)+dis_2(j,x))\), find the minimum spanning tree of a complete bipartite graph
/d/hztg/contest/6716222721518607d314c04f/file/