題目鏈接

先將邊排序，這樣就可以按從小到大的順序維護生成樹，枚舉到一條未連通的邊就連上，已連通則(用當前更大的)替換掉路徑上最小的邊，這樣一定不會更差。
每次構成樹時更新答案。答案就是當前邊減去生成樹上最小邊的權值。
LCT上維護最小邊的編號。求最小邊把樹上的邊用vis[]標記即可。

不熟啊.

(另外暴力可以排序后枚舉一個分界點，在它之后求最小生成樹，在它之前求最大生成樹)

#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define INF 10000007
const int N=5e4+5,M=2e5+5,S=N+M;int n,m,_fa[N];
bool vis[M];
struct Edge
{int fr,to,val;Edge() {}Edge(int f,int t,int v): fr(f),to(t),val(v) {}bool operator <(const Edge &a)const {return val<a.val;}
}e[M];
namespace LCT
{#define lson son[x][0]#define rson son[x][1]int fa[S],son[S][2],sk[S],pos[S],val[S];bool tag[S];inline int Get(int x,int y){//取最小的邊 return val[x]<val[y]?x:y;}inline void Update(int x){pos[x]=Get(x,Get(pos[lson],pos[rson]));//是左右兒子的最小邊pos[]！}inline bool n_root(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}inline void Rev(int x){std::swap(lson,rson), tag[x]^=1;}void PushDown(int x){if(tag[x]) Rev(lson),Rev(rson),tag[x]=0;}void Rotate(int x){int a=fa[x],b=fa[a],l=son[a][1]==x,r=l^1;if(n_root(a)) son[b][son[b][1]==a]=x;if(son[x][r]) fa[son[x][r]]=a;fa[a]=x, fa[x]=b, son[a][l]=son[x][r], son[x][r]=a;Update(a);}void Splay(int x){int t=1,a=x; sk[1]=x;while(n_root(a)) sk[++t]=a=fa[a];while(t) PushDown(sk[t--]);while(n_root(x)){if(n_root(a=fa[x])) Rotate(son[a][1]==x^son[fa[a]][1]==a?x:a);Rotate(x);}Update(x);}void Access(int x){for(int pre=0; x; x=fa[pre=x])Splay(x), rson=pre, Update(x);}void Make_root(int x){Access(x), Splay(x), Rev(x);}void Split(int x,int y){Make_root(x), Access(y), Splay(y);}void Link(int x){Make_root(e[x].to), fa[fa[e[x].to]=x+N]=e[x].fr;}void Cut(int x){Access(e[x-N].to), Splay(x), lson=rson=fa[lson]=fa[rson]/*=fa[x]*/=0;//fa[x]應該是用不到吧。。注意更新順序！后更新lson,rson...}
}
using namespace LCT;inline int read()
{int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now;
}
int Get_fa(int x){return x==_fa[x]?x:_fa[x]=Get_fa(_fa[x]);
}int main()
{n=read(),m=read();val[0]=INF;//空節點！for(int i=1; i<=n; ++i) _fa[i]=i, val[i]=INF;//點有自己的權值，設為INF避免影響答案(最小邊) for(int u,v,w,i=1; i<=m; ++i) u=read(),v=read(),w=read(),e[i]=Edge(u,v,w);std::sort(e+1,e+1+m);
//  for(int i=1; i<=m; ++i) val[i+N]=e[i].val;int res=1e6;for(int p=1,x,y,k=1,i=1; i<=m; ++i){val[i+N]=e[i].val, x=e[i].fr, y=e[i].to;if(k<n && Get_fa(x)!=Get_fa(y)){_fa[_fa[x]]=_fa[y];//路徑壓縮后 Link(i), vis[i]=1;if(++k>=n) res=e[i].val-e[p].val;}else if(x!=y)//不要計算重邊 {Split(x,y);vis[pos[y]-N]=0, vis[i]=1;//別忘了Splay(y)后再用y的信息pos[y]！而且要先用pos[y]清vis再Cut().while(!vis[p]) ++p;Cut(pos[y]), Link(i);if(k>=n) res=std::min(res,e[i].val-e[p].val);}}printf("%d",res);return 0;
}

轉載于:https://www.cnblogs.com/SovietPower/p/8637929.html

總結

以上是生活随笔為你收集整理的洛谷.4234.最小差值生成树(LCT)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。