给定一个标号为从$1$到$n$的、有$m$条边的无向图，求边权最大值与最小值的差值最小的生成树。

做法类似魔法森林，首先求出来最小生成树，然后每次加入一条边，断掉环上最小边并更新答案

这个过程我用两个堆维护的

代码：

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #define M 500010  7 #define ls ch[x][0]  8 #define rs ch[x][1]  9 using namespace std; 10 int n,m,ans,top,cnt; 11 int st[M],f[M],fa[M],rev[M],minn[M],val[M],id[M],ch[M][2]; 12 struct node{
   int v;}; 13 priority_queue
          
           q1,q2; 14 bool operator < (node a1,node a2) { 15 return a1.v>a2.v; 16 } 17 void heap_pop(int v) { 18 q1.push((node){v}); 19 } 20 void heap_push(int v) { 21 q2.push((node){v}); 22 } 23 int heap_top() { 24 while(!q1.empty()) { 25 int x1=q1.top().v,x2=q2.top().v; 26 if(x1==x2) q1.pop(),q2.pop(); 27 else break; 28 } 29 return q2.top().v; 30 } 31 struct point{ 32 int u,v,w; 33 }a[M]; 34 bool cmp(point a1,point a2) { 35 return a1.w
           
            =1;i--) pushdown(st[i]); 69 for(int fa;!is_root(x);rotate(x)) 70 if(!is_root(fa=f[x])) 71 rotate(get(x)==get(fa)?fa:x); 72 } 73 void access(int x) { 74 for(int y=0;x;y=x,x=f[x]) 75 splay(x),ch[x][1]=y,update(x); 76 } 77 void makeroot(int x) { 78 access(x);splay(x);rev[x]^=1; 79 } 80 void spilt(int x,int y) { 81 makeroot(x);access(y);splay(y); 82 } 83 void link(int x,int y) { 84 makeroot(x);f[x]=y;splay(x); 85 } 86 void cut(int x,int y) { 87 spilt(x,y);f[x]=ch[y][0]=0; 88 } 89 int query(int x,int y) { 90 spilt(x,y);return id[y]; 91 } 92 int main() { 93 scanf("%d%d",&n,&m); 94 for(int i=1;i<=m;i++) 95 scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); 96 sort(a+1,a+1+m,cmp); 97 memset(minn,63,sizeof(minn)); 98 memset(val,63,sizeof(val)); 99 memset(&ans,0x7f,sizeof(ans));100 for(int i=1;i<=n;i++) fa[i]=i;101 for(int i=1;i<=m;i++) id[i+n]=i+n,val[i+n]=a[i].w;102 for(int i=1;i<=m;i++) {103 int x=a[i].u,y=a[i].v;104 if(find(x)==find(y)) {105 int ID=query(x,y);106 cut(a[ID-n].u,ID),cut(a[ID-n].v,ID);107 link(x,i+n),link(y,i+n);108 heap_pop(val[ID]);109 heap_push(val[i+n]);110 }111 else {112 fa[find(x)]=find(y);113 link(x,i+n),link(y,i+n);114 heap_push(val[i+n]);115 cnt++;116 }117 if(cnt==n-1) {118 ans=min(ans,a[i].w-heap_top());119 }120 }121 printf("%d\n",ans);122 return 0;123 }