P4234-最小差值生成树【LCT】

news/2024/11/21 1:28:54/

正题

题目链接:https://www.luogu.com.cn/problem/P4234


题目大意

给出 n n n个点 m m m条边的一张图。求一棵生成树使得最大边权减去最小边权最小。

1 ≤ n ≤ 5 × 1 0 4 , 1 ≤ m ≤ 2 × 1 0 5 1\leq n\leq 5\times 10^4,1\leq m\leq 2\times 10^5 1n5×104,1m2×105


解题思路

按照边权排序,然后像魔法森林一样用 L C T LCT LCT维护最小生成树就好了。

没啥别的,练练手而已。时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)


code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int N=3e5+10;
struct node{int x,y,w;
}e[N];
int n,m,p[N],fa[N];bool v[N];
struct LCT{int fa[N],t[N][2];bool r[N];stack<int> s;bool Nroot(int x){return fa[x]&&(t[fa[x]][0]==x||t[fa[x]][1]==x);}bool Direct(int x){return t[fa[x]][1]==x;}void PushUp(int x){p[x]=min(min(p[t[x][0]],p[t[x][1]]),x);return;}void Rev(int x){r[x]^=1;swap(t[x][0],t[x][1]);return;}void PushDown(int x){if(r[x])Rev(t[x][0]),Rev(t[x][1]),r[x]=0;return;}void Rotate(int x){int y=fa[x],z=fa[y];int xs=Direct(x),ys=Direct(y);int w=t[x][xs^1];t[y][xs]=w;t[x][xs^1]=y;if(Nroot(y))t[z][ys]=x;if(w)fa[w]=y;fa[y]=x;fa[x]=z;PushUp(y);PushUp(x);return;}void Splay(int x){int y=x;s.push(x);while(Nroot(y))y=fa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){int y=fa[x];if(!Nroot(y))Rotate(x);else if(Direct(x)==Direct(y))Rotate(y),Rotate(x);else Rotate(x),Rotate(x);}return;}void Access(int x){for(int y=0;x;y=x,x=fa[x])Splay(x),t[x][1]=y,PushUp(x);return;}void MakeRoot(int x){Access(x);Splay(x);Rev(x);return;}int Split(int x,int y){MakeRoot(x);Access(y);Splay(y);return p[y];}void Link(int x,int y){MakeRoot(x);fa[x]=y;Access(x);return;}void Cut(int x,int y){MakeRoot(x);Access(y);Splay(y);fa[t[y][0]]=0;t[y][0]=0;PushUp(y);return;}
}T;
int find(int x)
{return (fa[x]==x)?x:(fa[x]=find(fa[x]));}
bool cmp(node x,node y)
{return x.w<y.w;}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);sort(e+1,e+1+m,cmp);memset(p,0x3f,sizeof(p)); for(int i=1;i<=n+m;i++)fa[i]=p[i]=i;int k=n,z=0,ans=1e5;for(int i=1;i<=m;i++){int x=e[i].x,y=e[i].y;if(x==y)continue;int fx=find(x),fy=find(y);if(fx==fy){int num=T.Split(x+m,y+m);T.Cut(e[num].x+m,num);T.Cut(num,e[num].y+m);v[num]=0;}else fa[fx]=fy,k--;T.Link(x+m,i);T.Link(i,y+m);v[i]=1;while(!v[z])z++;if(k==1)ans=min(ans,e[i].w-e[z].w);}printf("%d\n",ans);return 0;
}

http://www.ppmy.cn/news/356267.html

相关文章

洛谷 p4234 最小差值生成树

题意题解 题意 求最长边与最短边差值最小的生成树. 题解 LCT裸题. 将边按照边权从小到大排序,产生生成树的同时立即更新答案. 如果加入一条边的时候出现了环,把环上最小的边去掉加入该边. 每次跑最小值即可,用LCT可以较方便地维护. 为什么RE了啊啊啊啊啊啊啊啊啊!!!!!!…

【洛谷P4234】最小差值生成树

Description 给定一张n个点&#xff0c;m条边的无向图&#xff0c;求出边权最大值和最小值差值最小的生成树 Solution LCT并查集 按照最小生成树的思路&#xff0c;先将边按照边权从小到大排序&#xff0c;然后顺序考虑每一条边 如果当前这条边的两个端点没有连通&#xff0c;那…

luogu 4234 最小差值生成树 LCT

感觉码力严重下降~ #include <bits/stdc.h> #define N 400006 #define inf 1000000000 #define setIO(s) freopen(s".in","r",stdin) using namespace std; multiset<int>S; multiset<int>::iterator it; struct…

洛谷P4234 最小差值生成树

LCT维护生成树 把边从小到大排序&#xff0c;然后一条一条加边&#xff0c;如果成环就把环上最小的删了&#xff0c;我们得到的第一个生成树就是最小生成树。 然后之后每一条边都比前面的生成树的最大边大&#xff0c;我们用这条边的权值减去生成树里最小的&#xff0c;更新答案…

洛谷 P4234 LCT + 排序 + 枚举

求边权最大值与最小值的差值最小的生成树&#xff0c;输出这个差值大小。 按权值排序&#xff0c;我们等同于枚举最大值&#xff0c;然后更新生成树让生成树的最小值尽可能最大。 也就是每次加入边&#xff0c;若构成环&#xff0c;则去掉环上最小值。 若加入边不会构成环&…

LuoguP4234_最小差值生成树_LCT

LuoguP4234_最小差值生成树_LCT 题意&#xff1a; 给出一个无向图&#xff0c;求最大的边权减最小的边权最小的一棵生成树。 分析&#xff1a; 可以把边权从大到小排序&#xff0c;然后类似魔法森林那样插入。 如果两点不连通&#xff0c;直接连上&#xff0c;否则找到两点间最…

NKOJ 4234 三角分形

问题描述 今天何老板得到了一个神奇的正三角形&#xff0c;它具有自动分形技能。 一天后&#xff0c;它会分成4个相同的正三角形&#xff0c;其中三个“尖尖”朝上&#xff0c;一个“尖尖”朝下。 一天后&#xff0c;里面的每个三角形又会按上述规则分形下去。 如此反复………

[luogu4234]最小差值生成树

[luogu4234]最小差值生成树 luogu 从小到大枚举边,并连接,如果已连通就删掉路径上最小边 lct维护\(ansmin(E_{max}-E_{min})\) #include<bits/stdc.h> using namespace std; const int _4e55; int re(){int x0,w1;char chgetchar();while(ch<0||ch>9){if(ch-)w-1;c…