题目描述
因为一场不小的地震， Y 省 n 个城市之间的道路都损坏掉了，省长希望小 X 将城市之间的道路重 修一遍。 很多城市之间的地基都被地震破坏导致不能修路了，因此可供修建的道路只有 m 条。因为施工队伍 有限，省长要求用尽量少的道路将所有的城市连通起来，这样施工量就可以尽量少。不过，省长为了表 示自己的公正无私，要求在满足上述条件的情况下，选择一种方案，使得该方案中最贵道路的价格和最 便宜道路的价格的差值尽量小，即使这样的方案会使总价提升很多也没关系。 小 X 现在手忙脚乱，希望你帮帮他。
输入
第一行包含两个整数 n; m。 接下来 m 行，每行包含三个整数 a; b; c，表示城市 a; b 之间可以修建一条价格为 c 的无向道路。
输出
若存在合法方案，则第一行包含一个整数，表示最贵道路的价格和最便宜道路的价格的最小差值； 否则第一行包含一个整数 −1。
样例输入
5 10
1 2 9384
1 3 887
1 4 2778
1 5 6916
2 3 7794
2 4 8336
2 5 5387
3 4 493
3 5 6650
4 5 1422
样例输出
1686
LCT 裸题。
#pragma GCC optimize("-Ofast") #include<bits/stdc++.h> #define N 910007 using namespace std; int n,m,ans=INT_MAX,ti; void read(int &x){ static char c; static int b; for (b=1,c=getchar();!isdigit(c);c=getchar()) if (c=='-') b=-1; for (x=0;isdigit(c);c=getchar()) x=x*10+c-48; x*=b; } struct edge{ int x,y,z; inline bool operator <(const edge& A)const{ return z<A.z; } }e[N]; namespace snow{ int ch[N][2],fa[N],r[N],mi[N],val[N],id,usd[N]; bool isroot(int x){ return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x; } void rev(int x){ r[x]^=1; swap(ch[x][0],ch[x][1]); } void pushdown(int x){ if (!isroot(x)) pushdown(fa[x]); if (r[x]) { if (ch[x][0]) rev(ch[x][0]); if (ch[x][1]) rev(ch[x][1]); r[x]=0; } } void pushup(int x){ mi[x]=val[mi[ch[x][0]]]<val[mi[ch[x][1]]]?mi[ch[x][0]]:mi[ch[x][1]]; mi[x]=val[mi[x]]<val[x]?mi[x]:x; } void rotate(int x){ int y=fa[x],z=fa[y],l,r; if (ch[y][0]==x) l=0; else l=1; r=l^1; if (!isroot(y)) ch[z][ch[z][1]==y]=x; fa[x]=z; fa[ch[x][r]]=y; fa[y]=x; ch[y][l]=ch[x][r]; ch[x][r]=y; pushup(x); pushup(y); } void splay(int x){ pushdown(x); while (!isroot(x)) { int y=fa[x],z=fa[y]; if (!isroot(y)) { if (ch[y][0]==x^ch[z][0]==y) rotate(x); else rotate(y);} rotate(x); } } void access(int x) { int y=0; while (x) { splay(x); ch[x][1]=y; pushup(x); y=x; x=fa[x]; } } void beroot(int x){ access(x); splay(x); rev(x); } int root(int x) { access(x); splay(x); while (ch[x][0]) x=ch[x][0]; return x; } void link(int x,int y){ beroot(x); fa[x]=y; } void cut(int x,int y){ beroot(x); access(y); splay(y); if (ch[y][0]==x) ch[y][0]=0; fa[x]=0; } void sol() { for (int i=1;i<=m;i++) read(e[i].x),read(e[i].y),read(e[i].z); sort(e+1,e+m+1); ans=INT_MAX; for (int i=0;i<=n;i++) val[i]=INT_MAX; for (int i=1;i<=m;i++) val[n+i]=e[i].z; int to=1; for (int i=1;i<=m;i++) { beroot(e[i].x); if (root(e[i].y)!=e[i].x) { link(n+i,e[i].x); link(n+i,e[i].y); ti++; }else { id=mi[e[i].y]; usd[id-n]=1; cut(id,e[id-n].x); cut(id,e[id-n].y); link(n+i,e[i].x); link(n+i,e[i].y); } while (usd[to]) to++; if (ti==n-1) ans=min(ans,e[i].z-e[to].z); } printf("%d ",ans==INT_MAX?-1:ans); } } signed main () { read(n); read(m); snow::sol(); }