BZOJ3669 [Noi2014]魔法森林 LCT

歡迎通路~原文出處——部落格園-zhouzhendong

去部落格園看該題解

題目傳送門 - BZOJ3669

題意概括

　　有一個無向圖，每條邊分别有a、b兩種權值。

　　你要通過他，那麼你自身的a、b兩種權值必須得都不小于該邊。

　　現在你要從1走到n，問你自身的a+b最小為多少。

題解

　　我們可以按照a排序。

　　然後依次加邊。

　　那麼目前最大的a就是目前加入邊的a。

　　至于b，我們可以寫LCT來維護。

　　我們在加入一條邊的時候，要判斷目前的邊連接配接的兩個點是否連通。

　　如果不連通，那麼直接加入此邊。

　　如果連通，那麼要找出兩點之間的樹鍊的最大邊權b，然後在目前邊和那條邊中選擇b小的留下。

　　每次更新答案，隻需要判斷1和n是否連通然後求一下值就可以了，應該是很簡單的。

　　至于聽的一頭霧水的同學們，如何維護邊？？那麼，建議你看看這個↓

　　BZOJ2594 [Wc2006]水管局長資料加強版 LCT kruskal

代碼

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int N=50005,M=100005,S=N+M;
int n,m;
int fa[S],son[S][2],rev[S],Max[S],val[S];
struct Edge{
	int x,y,a,b;
	void read(){
		scanf("%d%d%d%d",&x,&y,&a,&b);
	}
}e[M];
void clear(int x,int v){
	fa[x]=son[x][0]=son[x][1]=rev[x]=0;
	Max[x]=val[x]=v;
}
bool isroot(int x){
	return son[fa[x]][1]!=x&&son[fa[x]][0]!=x;
}
void pushup(int x){
	int ls=son[x][0],rs=son[x][1];
	Max[x]=e[Max[ls]].b>e[Max[rs]].b?Max[ls]:Max[rs];
	Max[x]=e[val[x]].b>e[Max[x]].b?val[x]:Max[x];
}
void pushdown(int x){
	if (rev[x]){
		rev[x]=0;
		rev[son[x][0]]^=1;
		rev[son[x][1]]^=1;
		swap(son[x][0],son[x][1]);
	}
}
void pushadd(int x){
	if (!isroot(x))
		pushadd(fa[x]);
	pushdown(x);
}
int wson(int x){
	return son[fa[x]][1]==x;
}
void rotate(int x){
	if (isroot(x))
		return;
	int y=fa[x],z=fa[y],L=wson(x),R=L^1;
	if (!isroot(y))
		son[z][wson(y)]=x;
	fa[x]=z,fa[y]=x,fa[son[x][R]]=y;
	son[y][L]=son[x][R],son[x][R]=y;
	pushup(y),pushup(x);
}
void splay(int x){
	pushadd(x);
	for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])
		if (!isroot(y))
			rotate(wson(x)==wson(y)?y:x);
}
void access(int x){
	for (int t=0;x;t=x,x=fa[x]){
		splay(x);
		son[x][1]=t;
		pushup(x);
	}
}
void rever(int x){
	access(x);
	splay(x);
	rev[x]^=1;
}
void link(int x,int y){
	rever(x);
	fa[x]=y;
}
void split(int x,int y){
	rever(y);
	access(x);
	splay(x);
}
void cut(int x,int y){
	split(x,y);
	fa[y]=son[x][0]=0;
}
int find(int x){
	access(x);
	splay(x);
	while (son[x][0])
		x=son[x][0];
	return x;
}
bool cmp(Edge a,Edge b){
	return a.a<b.a;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
		e[i].read();
	sort(e+1,e+m+1,cmp);
	e[0].b=0;
	for (int i=1;i<=n+m;i++)
		clear(i,0);
	int ans=2333333;
	for (int i=1;i<=m;i++){
		int a=e[i].a,b=e[i].b,x=e[i].x,y=e[i].y;
		if (x==y)
			continue;
		bool flag=1;
		if (find(x)==find(y)){
			split(x,y);
			int ce=Max[x];
			if (e[ce].b>b){
				cut(e[ce].x,ce+n);
				cut(e[ce].y,ce+n);
			}
			else 
				flag=0;
		}
		if (flag){
			clear(i+n,i);
			link(x,i+n);
			link(y,i+n);
		}
		if (find(1)==find(n)){
			split(1,n);
			int ne=Max[1];
			ans=min(ans,a+e[ne].b);
		}
	}
	printf("%d",ans==2333333?-1:ans);
	return 0;
}
           

　　

轉載于:https://www.cnblogs.com/zhouzhendong/p/BZOJ3669.html