UOJ#14【UER#1】DZY Loves Graph

122 阅读 0 评论 81 点赞

我是靠谱客的博主欢喜火龙果，这篇文章主要介绍UOJ#14【UER#1】DZY Loves Graph，现在分享给大家，希望可以做个参考。

题目链接：http://uoj.ac/problem/14

【分析】

先请允许我诚意地orz DZY神犇...

UOJ的题解真的很良心...http://vfleaking.blog.uoj.ac/blog/15

主要内容就是一个按秩合并的并查集，支持删边加边。在没有Return操作的情况下，这么做是nlogn的，已经足够了，但是有Return操作，在删完大量的边后重新加边会使时间复杂度变成n^2。

这时考虑离线处理，在进行Delete操作之前看看下一个操作是不是Return，如果不是就删边，如果是就不要删边，事先用一个数组Res[i]记录一下图中边数为i时最小生成树的大小，本次Delete操作的结果就是Res[当前图中边数-删去的边数]。

【代码】

复制代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=500010;

char cor[maxn][10];
int corx[maxn],cory[maxn];
int size[maxn],f[maxn],Ef[maxn];
int Q[maxn],tail;
LL Res[maxn];
int n,m;

void Init()
{
	scanf("%d%d",&n,&m);
	int x,y;
	for (int i=1;i<=m;i++)
	{
		scanf("%s",cor[i]);
		if (cor[i][0]=='A') scanf("%d%d",&corx[i],&cory[i]);
		else if (cor[i][0]=='D') scanf("%d",&corx[i]);
	}
}

int Find(int x) {return (f[x]==x)?x:Find(f[x]);}

void Add_Edge(int x,int y,int d)
{
	int px=Find(x),py=Find(y);
	Q[tail++]=d;
	if (px==py) {Ef[d]=-1;return;}
	if (size[px]>size[py]) swap(px,py);
	f[px]=py;
	for (int i=py;;py=f[py])
	{
		size[py]+=size[px];
		if (f[py]==py) break;
	}
	Ef[d]=px;
}

void Delete(int p)
{
	for (int px=f[p];;px=f[px])
	{
		size[px]-=size[p];
		if (f[px]==px) break;
	}
	f[p]=p;
}

void Solve()
{
	int tot=0,trcnt=0;
	LL ans=0;
	for (int i=1;i<=n;i++) f[i]=i,size[i]=1;
	for (int i=1;i<=m;i++)
	if (cor[i][0]=='A')
	{
		Add_Edge(corx[i],cory[i],i);
		if (Ef[i]!=-1) ans+=i,trcnt++;
		Res[++tot]=(trcnt<n-1)?0:ans;
		printf("%lldn",Res[tot]);
		if (cor[i+1][0]=='R') cor[i+1][0]='D',corx[i+1]=1;
	}
	else if (cor[i][0]=='D')
	{
		if (cor[i+1][0]=='R') {printf("%lldn%lldn",Res[tot-corx[i]],Res[tot]);continue;}
		while (corx[i]--)
		{
			int p=Q[--tail];tot--;
			if (Ef[p]==-1) continue;
			Delete(Ef[p]);
			ans-=p;trcnt--;
		}
		Res[tot]=(trcnt<n-1)?0:ans;
		printf("%lldn",Res[tot]);
	}
}

int main()
{
	Init();
	Solve();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=500010;

char cor[maxn][10];
int corx[maxn],cory[maxn];
int size[maxn],f[maxn],Ef[maxn];
int Q[maxn],tail;
LL Res[maxn];
int n,m;

void Init()
{
	scanf("%d%d",&n,&m);
	int x,y;
	for (int i=1;i<=m;i++)
	{
		scanf("%s",cor[i]);
		if (cor[i][0]=='A') scanf("%d%d",&corx[i],&cory[i]);
		else if (cor[i][0]=='D') scanf("%d",&corx[i]);
	}
}

int Find(int x) {return (f[x]==x)?x:Find(f[x]);}

void Add_Edge(int x,int y,int d)
{
	int px=Find(x),py=Find(y);
	Q[tail++]=d;
	if (px==py) {Ef[d]=-1;return;}
	if (size[px]>size[py]) swap(px,py);
	f[px]=py;
	for (int i=py;;py=f[py])
	{
		size[py]+=size[px];
		if (f[py]==py) break;
	}
	Ef[d]=px;
}

void Delete(int p)
{
	for (int px=f[p];;px=f[px])
	{
		size[px]-=size[p];
		if (f[px]==px) break;
	}
	f[p]=p;
}

void Solve()
{
	int tot=0,trcnt=0;
	LL ans=0;
	for (int i=1;i<=n;i++) f[i]=i,size[i]=1;
	for (int i=1;i<=m;i++)
	if (cor[i][0]=='A')
	{
		Add_Edge(corx[i],cory[i],i);
		if (Ef[i]!=-1) ans+=i,trcnt++;
		Res[++tot]=(trcnt<n-1)?0:ans;
		printf("%lldn",Res[tot]);
		if (cor[i+1][0]=='R') cor[i+1][0]='D',corx[i+1]=1;
	}
	else if (cor[i][0]=='D')
	{
		if (cor[i+1][0]=='R') {printf("%lldn%lldn",Res[tot-corx[i]],Res[tot]);continue;}
		while (corx[i]--)
		{
			int p=Q[--tail];tot--;
			if (Ef[p]==-1) continue;
			Delete(Ef[p]);
			ans-=p;trcnt--;
		}
		Res[tot]=(trcnt<n-1)?0:ans;
		printf("%lldn",Res[tot]);
	}
}

int main()
{
	Init();
	Solve();
	return 0;
}