【bzoj3669】魔法森林

Solution

　　愉悦智力康复ing

　　这题的话有两个比较关键的地方

　　首先是答案肯定是原图的某个生成树上的一条路径，那么我们考虑怎么来找这个生成树，因为关键值有两个，所以我们这里可以采取这样的一个方式：先对其中一个关键值排序

　　我们先将所有的边按照\(a\)值排序，然后按顺序加边，如果说当前这条边连接的两个点已经连通了，那么我们要考虑删掉一条边或者干脆不加这条边

　　这里我们可以用一个贪心的思想，删边的话肯定是删当前的边中\(b\)最大的那个（如果要加的那条边的\(b\)是最大的那么我们就不加这条边），如果说我们加了这条边并且\(1\)和\(n\)连通了，那么可以用当前最大的\(b\)+当前的\(a\)来更新答案（因为\(a\)是升序排列的，所以当前的\(a\)一定是最大的）

　　接着是第二部分，如何维护\(b\)的最大值？

　　又要删边又要加边的维护的又是链的数据，那当然是LCT咯qwq，但是因为这个地方我们是要维护边权，所以我们将每一条边变成一个点，然后其他的就全部都是常规操作了ovo

　　好像是比较套路的一题qwq

　　代码大概长这个样子

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mp make_pair

#define Pr pair<int,int>

using namespace std;

const int N=50010,M=100010,L=N+M;

const int inf=2147483647;

struct Rec{

	int a,b,x,y,id;

	friend bool operator <(Rec x,Rec y){return x.a<y.a;}

}a[M];

int n,m,ans;

namespace Lct{/*{{{*/

	int ch[L][2],fa[L],mx[L],loc[L],rev[L];

	int b[L];

	int tot;

	bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}

	int which(int x){return ch[fa[x]][1]==x;}

	void reverse(int x){

		swap(ch[x][0],ch[x][1]);

		rev[x]^=1;

	}

	void pd(int x){

		if (rev[x]){

			if (ch[x][0]) reverse(ch[x][0]);

			if (ch[x][1]) reverse(ch[x][1]);

			rev[x]=0;

		}

	}

	void pushdown(int x){

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

		pd(x);

	}

	void pushup(int x){

		mx[x]=b[x]; loc[x]=x;

		if (ch[x][0]){

			if (mx[ch[x][0]]>mx[x])

				mx[x]=mx[ch[x][0]],loc[x]=loc[ch[x][0]];

		}

		if (ch[x][1]){

			if (mx[ch[x][1]]>mx[x])

				mx[x]=mx[ch[x][1]],loc[x]=loc[ch[x][1]];

		}

	}

	void rotate(int x){

		int dir=which(x),f=fa[x];

		if (!isroot(f)) ch[fa[f]][which(f)]=x;

		if (ch[x][dir^1]) fa[ch[x][dir^1]]=f;

		fa[x]=fa[f];

		ch[f][dir]=ch[x][dir^1];

		ch[x][dir^1]=f; fa[f]=x;

		pushup(f);

		pushup(x);

	}

	void splay(int x){

		pushdown(x);

		for (int f=fa[x];!isroot(x);f=fa[x]){

			if (!isroot(f))

				rotate(which(f)==which(x)?f:x);

			rotate(x);

		}

	}

	void access(int x){

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

			splay(x);

			ch[x][1]=last;

			pushup(x);

		}

	}

	void make_rt(int x){

		access(x);

		splay(x);

		reverse(x);

	}

	bool connected(int x,int y){

		if (x==y) return true;

		make_rt(x);

		access(y);

		splay(y);

		return fa[x];

	}

	bool check(int x,int y){

		make_rt(x);

		access(y);

		splay(y);

		return ch[y][0]==x;

	}

	void cut(int x,int y){

		//printf("Cut %d %d\n",x,y);

		make_rt(x);

		access(y);

		splay(y);

		fa[x]=0;

		ch[y][0]=0;

		pushup(y);

	}

	Pr query(int x,int y){

		make_rt(x);

		access(y);

		splay(y);

		return mp(mx[y],loc[y]);

	}

	void link(int x,int y){

		//printf("Link %d %d\n",x,y);

		make_rt(y);

		fa[y]=x;

		pushup(x);

	}

	void Link(int x,int y,int bian,int vala){

		int tmp;

		if (x==y) return;

		if (connected(x,y)){

			tmp=query(x,y).second;

			if (b[bian]<b[tmp]){

				cut(a[tmp-n].x,tmp);

				cut(a[tmp-n].y,tmp);

				link(x,bian);

				link(y,bian);

			}

		}

		else{

			link(x,bian);

			link(y,bian);

		}

		if (connected(1,n)){

			tmp=query(1,n).first;

			ans=min(ans,tmp+vala);

		}

	}

}/*}}}*/

void build(){

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

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

		a[i].id=i+n;

		Lct::b[a[i].id]=a[i].b;

		Lct::pushup(a[i].id);

	}

}

void solve(){

	ans=inf;

	int tmp=0;

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

		Lct::Link(a[i].x,a[i].y,a[i].id,a[i].a);

		//printf("%d\n",ans);

	}

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

	else printf("-1\n");

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

#endif

	scanf("%d%d",&n,&m);

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

		scanf("%d%d%d%d\n",&a[i].x,&a[i].y,&a[i].a,&a[i].b);

	}

	build();

	//for (int i=1;i<=m;++i) printf("%d %d %d %d\n",a[i].x,a[i].y,a[i].a,a[i].b);

	solve();

}

巴特西

【bzoj3669】魔法森林

Solution

最新文章

热门文章