学校网站建设项目需求报告,南阳建网站企业有哪些,动画制作专业培训,宝塔本地wordpress正题
题目链接:https://www.luogu.com.cn/problem/P4234 题目大意
给出nnn个点mmm条边的一张图。求一棵生成树使得最大边权减去最小边权最小。 1≤n≤5104,1≤m≤21051\leq n\leq 5\times 10^4,1\leq m\leq 2\times 10^51≤n≤5104,1≤m≤2105 解题思路
按照边权排序#x…正题
题目链接:https://www.luogu.com.cn/problem/P4234 题目大意
给出nnn个点mmm条边的一张图。求一棵生成树使得最大边权减去最小边权最小。
1≤n≤5×104,1≤m≤2×1051\leq n\leq 5\times 10^4,1\leq m\leq 2\times 10^51≤n≤5×104,1≤m≤2×105 解题思路
按照边权排序然后像魔法森林一样用LCTLCTLCT维护最小生成树就好了。
没啥别的练练手而已。时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N3e510;
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];stackint 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 yfa[x],zfa[y];int xsDirect(x),ysDirect(y);int wt[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 yx;s.push(x);while(Nroot(y))yfa[y],s.push(y);while(!s.empty())PushDown(s.top()),s.pop();while(Nroot(x)){int yfa[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 y0;x;yx,xfa[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.wy.w;}
int main()
{scanf(%d%d,n,m);for(int i1;im;i)scanf(%d%d%d,e[i].x,e[i].y,e[i].w);sort(e1,e1m,cmp);memset(p,0x3f,sizeof(p)); for(int i1;inm;i)fa[i]p[i]i;int kn,z0,ans1e5;for(int i1;im;i){int xe[i].x,ye[i].y;if(xy)continue;int fxfind(x),fyfind(y);if(fxfy){int numT.Split(xm,ym);T.Cut(e[num].xm,num);T.Cut(num,e[num].ym);v[num]0;}else fa[fx]fy,k--;T.Link(xm,i);T.Link(i,ym);v[i]1;while(!v[z])z;if(k1)ansmin(ans,e[i].w-e[z].w);}printf(%d\n,ans);return 0;
}
