[AGC002D] Stamp Rally （并查集+整体二分）

Description

给你一个n个点m个条边构成的简单无向连通图，有Q组询问，每次询问从两个点x,y走出两条路径，使这两条路径覆盖z个点，求得一种方案使得路径上经过的变的最大编号最小。

Input

第一行两个整数n,m，如题目所述

接下来m行，每行两个整数x,y描述一条边

接下来一个整数Q，如题目所述

接下来Q行，每行三个整数x,y,z，如题目描述

Output

Q行，每行一个正整数，如题目描述

题解：

先想一想，可以用并查集解决，但 \(n^2\) 太慢了，于是就想到了整体二分。

我先是用了一个普通的并查集，结果发现每次都要初始化一遍，T 飞了。

后来想着可以支持删除，就不能路径压缩了（还是T飞），我了解到了一个黑科技，按秩合并。

我们合并两棵树的时候，我们把树高小的挂在树高大的下面，这样就能把树高控制在log级别。

然后我们加边的时候，用栈记录合并的两个节点，分完之后，再从栈中一个个地取出来恢复原样就好了。

到最后一个点的时候我们再把这条边连上，成功AC。

对了，我之前加了这个剪枝：

if(x<y)return;

就是说如果区间里没有数就不往下了，但这会导致有些边没有连，就WA了。

CODE：

#include<iostream>

#include<stack>

#include<cstdio>

using namespace std;

int n,m,q,ans[100005];

int siz[100005],fa[100005];

struct Edge{

	int x,y;

}e[100005];

struct Question{

	int x,y,z,id;

}Q[100005],tmp[100005];

stack<Edge> s;

int find(int x){

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

	return find(fa[x]);

}

void solve(int l,int r,int x,int y){

	if(l==r){

		for(int i=x;i<=y;i++)ans[Q[i].id]=l;

		int fx=find(e[l].x),fy=find(e[l].y);

		if(siz[fx]>siz[fy])swap(fx,fy);

		if(fx!=fy)fa[fx]=fy,siz[fy]+=siz[fx];

		return;

	}

	int mid=l+r>>1;

	for(int i=l;i<=mid;i++){

		int fx=find(e[i].x),fy=find(e[i].y);

		if(siz[fx]>siz[fy])swap(fx,fy);

		if(fx!=fy){

			fa[fx]=fy,siz[fy]+=siz[fx];

			s.push((Edge){fx,fy});

		}

	}

	int tot1=x-1,tot2=0;

	for(int i=x,size;i<=y;i++){

		int fx=find(Q[i].x),fy=find(Q[i].y);

		if(fx==fy)size=siz[fx];

		else size=siz[fx]+siz[fy];

		if(size>=Q[i].z)Q[++tot1]=Q[i];

		else tmp[++tot2]=Q[i];

	}

	for(int i=1;i<=tot2;i++)Q[tot1+i]=tmp[i];

	while(!s.empty()){

		Edge e=s.top();s.pop();

		fa[e.x]=e.x,siz[e.y]-=siz[e.x];

	}

	solve(l,mid,x,tot1);

	solve(mid+1,r,tot1+1,y);

}

int main(){

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

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

		scanf("%d%d",&e[i].x,&e[i].y);

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

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

	scanf("%d",&q);

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

		scanf("%d%d%d",&Q[i].x,&Q[i].y,&Q[i].z);

		Q[i].id=i;

	}

	solve(1,m,1,q);

	for(int i=1;i<=q;i++)

		printf("%d\n",ans[i]);

}

巴特西

[AGC002D] Stamp Rally （并查集+整体二分）

Description

Input

Output

题解：

CODE：

最新文章

热门文章