首页 > 代码库 > 【BZOJ 2049】 [Sdoi2008]Cave 洞穴勘测

【BZOJ 2049】 [Sdoi2008]Cave 洞穴勘测

2024-08-07 15:29:15   222人阅读

2049: [Sdoi2008]Cave 洞穴勘测

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 3215  Solved: 1449
[Submit][Status]

Description

辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

Input

第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。

Output

对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）

Sample Input

样例输入1 cave.in
200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127
样例输入2 cave.in

3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3



Sample Output

样例输出1 cave.out
No
Yes
No


样例输出2 cave.out

Yes
No

HINT

数据说明 10%的数据满足n≤1000, m≤20000 20%的数据满足n≤2000, m≤40000 30%的数据满足n≤3000, m≤60000 40%的数据满足n≤4000, m≤80000 50%的数据满足n≤5000, m≤100000 60%的数据满足n≤6000, m≤120000 70%的数据满足n≤7000, m≤140000 80%的数据满足n≤8000, m≤160000 90%的数据满足n≤9000, m≤180000 100%的数据满足n≤10000, m≤200000 保证所有Destroy指令将摧毁的是一条存在的通道本题输入、输出规模比较大，建议c\c++选手使用scanf和printf进行I\O操作以免超时

Source

动态树


这道题一开始用LCT写一直RE，于是先用暴力写了一个，A掉之后发现自己对LCT完全理解了~


先说一下暴力的做法：

a[x].fa表示x的父亲。


Connect(x,y)：把x提到根，即把x一直到根的边全部反向变成x的孩子、孙子。。然后直接把x的父亲赋值为y就连在一起了。


<这完全就是LCT中Link操作的暴力做法，因此我理解了Cut为什么要把边反向了~>


Destroy(x,y):因为x,y之间有连边，所以x不是y的父亲，就是y的儿子，直接断开就行~


#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
int n,m,fa[10005];
int Getfather(int x)
{
	if (fa[x]==x) return x;
	return Getfather(fa[x]);
}
void Root(int x)
{
	if (fa[x]==x) return;
	Root(fa[x]);
	fa[fa[x]]=x;
}
void Link(int x,int y)
{
	Root(x),Root(y);
	fa[y]=y;
	fa[x]=y;
}
void Cut(int x,int y)
{
	if (fa[x]==y) fa[x]=x;
	else fa[y]=y;
}
int main()
{
	scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
		fa[i]=i;
	while (m--)
	{
		char str[20];
		int x,y;
		scanf("%s%d%d",str,&x,&y);
		switch(str[0])
		{
			case 'C':
				Link(x,y);
			    break;
			case 'D':
				Cut(x,y);
				break;
			case 'Q':
				if (Getfather(x)==Getfather(y)) printf("Yes\n");
				else printf("No\n");
				break;
		}
	}
	return 0;
}


(比LCT还要快。。)


LCT的做法就是模板了。。

（详见这里）


但要注意一点：

Splay前要把当前结点到根的所有的标记都Push_down！！


为什么之前写splay的时候边旋转边Push_down就可以了呢？


因为之前的Splay之前都要Findkth()在这个时候就已经把所有标记都Push_down了，而LCT中是直接旋转的，所以要先把所有标记下传。


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int root[50005],n,q;
struct lct
{
	int rev,l,r,fa;
}a[50005];
char str[20];
void Push_down(int x)
{
	if (!x||!a[x].rev) return;
	swap(a[x].l,a[x].r);
        a[a[x].l].rev^=1;
	a[a[x].r].rev^=1;
	a[x].rev=0;
}
void zig(int x)
{
	int y=a[x].fa;
	int z=a[y].fa;
	a[x].fa=z,a[y].fa=x;
	a[y].l=a[x].r,a[a[x].r].fa=y,a[x].r=y;
	if (root[y]) root[y]=0,root[x]=1;
	else 
	{
		if (y==a[z].l) a[z].l=x;
		else a[z].r=x;
	}
}
void zag(int x)
{
	int y=a[x].fa;
	int z=a[y].fa;
	a[x].fa=z,a[y].fa=x;
	a[y].r=a[x].l,a[a[x].l].fa=y,a[x].l=y;
	if (root[y]) root[y]=0,root[x]=1;
	else
	{
		if (y==a[z].l) a[z].l=x;
		else a[z].r=x;
	}
}
void P(int x)
{
	if (!root[x]) P(a[x].fa);
	Push_down(x);
}
void Splay(int x)
{
	P(x);
	while (!root[x])
	{
		int y=a[x].fa;
		int z=a[y].fa;
		if (root[y])
		{
			if (x==a[y].l) zig(x);
			else zag(x);
		}
		else if (a[z].l==y)
		{
			if (a[y].l==x) zig(y),zig(x);
			else zag(x),zig(x);
		}
		else
		{
			if (a[y].r==x) zag(y),zag(x);
			else zig(x),zag(x);
		}
	}
}
void Access(int x)
{
	int y=0;
	while (x)
	{
		Splay(x);
		root[a[x].r]=1;
		a[x].r=y;
		root[a[x].r]=0;
		y=x;
		x=a[x].fa;
	}
}
void Makeroot(int x)
{
	Access(x);
	Splay(x);
	a[x].rev^=1;
}
void Link(int u,int v)
{
	Makeroot(u);
	a[u].fa=v;
}
void Cut(int u,int v)
{
	Makeroot(u);
        Access(v);
	Splay(v);
	root[a[v].l]=1;
	a[a[v].l].fa=0;
	a[v].l=0;
}
bool same(int u,int v)
{
	while (a[u].fa) u=a[u].fa;
	while (a[v].fa) v=a[v].fa;
	return u==v;
}
int main()
{
	//freopen("cave.in","r",stdin);
	//freopen("cave.out","w",stdout);
        scanf("%d%d",&n,&q);
	for (int i=0;i<=n;i++)
	{
		a[i].fa=0;
		a[i].l=a[i].r=a[i].rev=0;
		root[i]=1;
	}
	while (q--)
	{
		int x,y;
		scanf("%s%d%d",str,&x,&y);
		switch(str[0])
		{
			case 'C':
				Link(x,y);
				break;
			case 'D':
				Cut(x,y);
				break;
			case 'Q':
				if (same(x,y)) printf("Yes\n");
				else printf("No\n");
				break;
		}
	}
	return 0;
}


做了两道LCT的题了，写了一篇总结，对LCT的思想有了一定的理解，但还算不上完全掌握，所以以后再多做几道题~

【BZOJ 2049】 [Sdoi2008]Cave 洞穴勘测


联系
我们