BZOJ 3669: [Noi2014]魔法森林(lct+最小生成树)

解题思路

　　\(lct\)维护最小生成树。我们首先按照\(a\)排序，然后每次加入一条边，在图中维护一棵最小生成树。用并查集判断一下\(1\)与\(n\)是否联通，如果联通的话就尝试更新答案。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int MAXN = 50005;

const int MAXM = 1000005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,m,ans=1e9,F[MAXN],val[MAXN+MAXM],num;

int xx[MAXN+MAXM],yy[MAXN+MAXM];

struct Edge{

	int x,y,a,b;

	friend bool operator<(const Edge A,const Edge B){

		return A.a<B.a;

	}

}edge[MAXM];

int Find(int x){

	if(x==F[x]) return x;

	return F[x]=Find(F[x]);

}

namespace lct{

	int fa[MAXN+MAXM],ch[MAXN+MAXM][2],Max[MAXN+MAXM];

	bool tag[MAXN+MAXM];

	inline void pushup(int x){

		Max[x]=x;

		if(val[Max[ch[x][0]]]>val[Max[x]]) Max[x]=Max[ch[x][0]];

		if(val[Max[ch[x][1]]]>val[Max[x]]) Max[x]=Max[ch[x][1]];

	}

	inline void pushdown(int x){

		if(tag[x]){

			tag[x]^=1;swap(ch[x][0],ch[x][1]);

			if(ch[x][0]) tag[ch[x][0]]^=1;

			if(ch[x][1]) tag[ch[x][1]]^=1;

		}

	}

	inline bool isroot(int x){

		return (x!=ch[fa[x]][0] && x!=ch[fa[x]][1]);

	}

	inline bool check(int x){

		return (x==ch[fa[x]][1]);

	}

	void pd(int x){

		if(!isroot(x)) pd(fa[x]);pushdown(x);

	}

	inline void rotate(int x){

		int y=fa[x],z=fa[y];bool chk=check(x);

		if(!isroot(y)) ch[z][check(y)]=x;

		ch[y][chk]=ch[x][chk^1];fa[ch[x][chk^1]]=y;

		ch[x][chk^1]=y;fa[y]=x;fa[x]=z;pushup(y);pushup(x);

	}

	inline void splay(int x){

		pd(x);

		for(;!isroot(x);rotate(x))

			if(!isroot(fa[x])) rotate(check(fa[x])==check(x)?fa[x]:x);

	}

	inline void access(int x){

		for(int y=0;x;y=x,x=fa[x])

			splay(x),ch[x][1]=y,pushup(x);

	}

	inline void makeroot(int x){

		access(x);splay(x);tag[x]^=1;

	}

	inline void link(int x,int y){

		makeroot(x);fa[x]=y;pushup(y);

	}

	inline void split(int x,int y){

		makeroot(x);access(y);splay(x);

	}

	inline void cut(int x,int y){

		makeroot(x);access(y);splay(y);

		fa[x]=ch[y][0]=0;pushup(y);

	}

}

int main(){

	n=rd(),m=rd();int x,y,a,b,A,u,v;

	for(int i=1;i<=n;i++) F[i]=i;num=n;

	for(int i=1;i<=m;i++){

		x=rd(),y=rd(),a=rd(),b=rd();

		edge[i].x=x,edge[i].y=y,edge[i].a=a,edge[i].b=b;

	}

	sort(edge+1,edge+1+m);

	for(int i=1;i<=m;i++){

		A=edge[i].a;x=edge[i].x,y=edge[i].y;

		u=Find(edge[i].x);v=Find(edge[i].y);

		if(u!=v){

			val[++num]=edge[i].b;lct::link(x,num);lct::link(num,y);

			xx[num]=x;yy[num]=y;F[u]=v;

		}

		else {

			lct::split(x,y);

			if(val[lct::Max[x]]>edge[i].b) {

				a=lct::Max[x];b=yy[lct::Max[x]];val[++num]=edge[i].b;

				lct::cut(xx[lct::Max[x]],lct::Max[x]);lct::cut(a,b);

				lct::link(x,num),lct::link(num,y);xx[num]=x;yy[num]=y;

			}

		}

		if(Find(1)==Find(n)){

			lct::split(1,n);

			ans=min(ans,A+val[lct::Max[1]]);

		}

	}

	if(ans!=1e9) printf("%d\n",ans);

	else puts("-1");

	return 0;

}

巴特西

BZOJ 3669: [Noi2014]魔法森林(lct+最小生成树)

解题思路

代码

最新文章

热门文章