正题

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

题目大意

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

\(1\leq n\leq 5\times 10^4,1\leq m\leq 2\times 10^5\)

解题思路

按照边权排序，然后像魔法森林一样用\(LCT\)维护最小生成树就好了。

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

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;

}

巴特西

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

正题

题目大意

解题思路

code

最新文章

热门文章