Boruvka 相关

Boruvka 确实有用喵~ 😎😎😎

UOJ#661. 【IOI2021】keys

首先对于每个点可以 $O(m)\ bfs$ 出点 $S$ 能到达多少点，但是我连这个都没想出来 🤡👈🤣

具体而言就是开一个 $point_i​$ 数组表示如果我有了类型 $i​$ 的钥匙我能立刻到达哪里，对于每一个取出队头的点，假设他的钥匙为 $x​$，那么就将 $point_x​$ 里面的点全部 push 进队列里面，然后遍历他的所有出边，若我现在有这条边所需的钥匙，那么就直接把另一个端点 push 进队列，否则将他加进 $point​$ 数组里面，重复操作即可。

考虑怎么优化这个东西，继续分析性质，发现：

1. 如果点 $u$ 可以走到 $v$，那么 $u$ 一定不是答案。
2. 如果点 $x$ 可以走到 $y$，点 $y$ 可以走到点 $z$，那么点 $x$ 一定能走到点 $z$，即上面的性质具有传递性。

这好像是废话（

不过无所谓，现在可以转化一下题意了 😆😆😆

给定一张 $n$ 个点，$m$ 条边的图，设从 $i$ 出发能到达的点的数量为 $sum_i$，对于每个点 $u$ 求 $[sum_u=\min\limits_{i=1}^n{sum_i}]$。（下面称为新图）

转化后的题意里面的点就是原题里面的点，$(u,v)​$ 这条边的含义是在原题意中 $u​$ 能到达 $v​$。

思考有什么点可以作为答案，发现只有在缩点后的 DAG 里面没有出边的点才有可能满足转化后的题意。（下面称为 DAG 图）

考虑原题的答案是什么，不难发现输出 $1$ 的点就是 DAG 图中没有出边的强连通分量在新图中对应的点。

现在要求的就是 DAG 图中没有出边的强连通分量了。

但是因为 $m$ 是 $n^2$ 级别的，不能直接建图，得整点 👍 的，不跟新图边数有关的东西。

然后就是 boruvka 的思想了，感觉不是人想到的 😭😭😭

首先将开 $n​$ 个集合，第 $i​$ 个集合里面有且仅有点 $i​$。

定义关键点为集合中每个点都能到达的点。（可以证明经过下面的操作后集合中一定有一个这样的点，就是告诉你先别急🙃）

我们对于每个集合维护任意一个关键点，现在对于每个集合没有被合并过（指在本次操作中）的关键点在原图上做 bfs （就是上文提到的），如果搜到了一个和关键点不在一个集合的点，那么就将这两个集合合并，不难发现新集合关键点就是搜到的集合的关键点，重复操作。

这样搜索下去，不难发现最后的关键点一定在 DAG 图中没有出边的强连通分量里面，这样再搜索一遍求出强连通分量里面的点就好了。

复杂度：

每个点在每此操作只会搜到 $1$ 次，复杂度 $O(m)$；

因为每次操作集合个数会减半，所以总复杂度是 $O(m\log n)$ 的，非常强。

代码非常好写

inline void init(int n){ for(int i=1;i<=n;i++) p[i]=i; }
inline int find(int x){ return x==p[x]?x:p[x]=find(p[x]); }
inline void clear(){
	for(int u:trash){
		has[key[u]]=vis[u]=0;
		for(PII A:g[u]) point[A.second].clear();
	}
	trash.clear();
}
inline void calc(){
	if(trash.size()<mn){
		mn=trash.size();
		ans.clear();
		for(int u:trash) ans.eb(u);
	}
	else if(trash.size()==mn){
		for(int u:trash) ans.eb(u);
	}
}
inline int bfs(int S){
	queue<int>q; q.push(S),vis[S]=1,has[key[S]]=1,trash.eb(S);
	while(q.size()){
		int u=q.front(); q.pop();
		for(int v:point[key[u]]){
			if(vis[v]) continue;
			q.push(v),vis[v]=1,has[key[v]]=1,trash.eb(v);
		}
		point[key[u]].clear(); 
		for(PII A:g[u]){
			int v=A.first,lim=A.second;
			if(vis[v]) continue;
			if(has[lim]){
				if(find(v)!=find(S)) return p[find(S)]=find(v),st[find(v)]=1,clear(),1;
				q.push(v),vis[v]=1,has[key[v]]=1,trash.eb(v);
			}
			else point[lim].eb(v);
		}
	}
	calc();
	return clear(),0;
}
vector<int> find_reachable(vector<int>A,vector<int>U,vector<int>V,vector<int>lim){
	n=A.size(),m=U.size();
	for(int i=1;i<=n;i++) key[i]=A[i-1];
	for(int i=0;i<m;i++) g[U[i]+1].eb(V[i]+1,lim[i]),g[V[i]+1].eb(U[i]+1,lim[i]);
	for(int i=1;i<=n;i++) p[i]=i;
	bool flag=1;
	while(flag){
		memset(st,0,sizeof(st));
		flag=0;
		for(int i=1;i<=n;i++){
			if(find(i)!=i||st[i]) continue;
			flag|=bfs(i);			
		}
	}
	res.resize(n);
	for(int u:ans) res[u-1]=1;
	return re

Loj#3155. 「JOI Open 2019」病毒实验

其实感觉和上面差不多了，主要就是 boruvka 的思想 😆😆😆

首先注意到题目中说的是：

如果 $U_{i,j}>0$，表示居民 $(i,j)$ 可能会感染 JOI 病毒。如果以下情况持续了 $U_{i,j}$ 个时段，这位居民就将在下一个时段感染 JOI 病毒：

持续！😅😅😅

不然这题还有啥呀

首先发现每个格子是否能被感染只跟四个邻居有关，所以可以预处理 $mx_S$ 表示当邻居的感染情况为 $S$ 时感染最长能持续 $mx_S$ 个时段。

跟上面一个题很类似，还是发现如果 $u$ 能感染 $v$，则 $u$ 不可能成为答案，并且感染是具有传递性的。

然后后面的就都跟上面的题一样了（

我不会告诉你我不想写了的

但是确实是一模一样的 😅😅😅

至于统计答案，根据上面说的性质，只可能是 DAG 图中没有出边的强连通分量里面的点。

就权当是双倍经验吧（

code：

inline void init(int n){
	for(int i=1;i<=n;i++){
		if(s[i]=='E') d[i]=0;
		else if(s[i]=='S') d[i]=1;
		else if(s[i]=='W') d[i]=2;
		else d[i]=3;
	}
	for(int s=1;s<(1<<4);s++){
		for(int i=1;i<=n;i++) flag[i]=(s>>d[i])&1;
		int sum=0,pre=0,suf=n+1;
		while(flag[pre+1]) pre++;
		while(flag[suf-1]) suf--;
		mx[s]=pre+n-suf+1;
		if(pre==n) mx[s]=INF;
		for(int i=1;i<=n;i++){
			if(flag[i]) sum++;
			else mx[s]=max(mx[s],sum),sum=0;
		}
		mx[s]=max(mx[s],sum);
	}
}
int p[M*M];
bool st[M*M];
inline int find(int x){ return x==p[x]?x:p[x]=find(p[x]); }
inline int id(int x,int y){ return (x-1)*m+y; }
bool vis[M*M];
vector<int>pos;
inline void clear(){ for(int x:pos) vis[x]=0; pos.clear(); }
inline int chk(int i,int j){
	if(!h[i][j]) return 0;
	int s=0;
	for(int k=0;k<4;k++){
		int x=i+dx[k],y=j+dy[k];
		if(x<=0||x>n||y<=0||y>m) continue;
		if(vis[id(x,y)]) s|=1<<k;
	}
	return mx[s]>=h[i][j];
}
inline int bfs(PII S){
	queue<PII>q; q.push(S);
	pos.eb(id(S.first,S.second)),vis[id(S.first,S.second)]=1;
	int sum=0;
	while(q.size()){
		int i=q.front().first,j=q.front().second; q.pop();
		sum++;
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k],A=find(id(x,y)),B=find(id(i,j));
			if(x<=0||x>n||y<=0||y>m||vis[id(x,y)]) continue;
			if(chk(x,y)){
				if(A!=B) return clear(),p[B]=A,st[A]=1,0;
				else q.push({x,y}),vis[id(x,y)]=1,pos.eb(id(x,y));
			}
		}
	}
	return clear(),sum;
}
int main(){
	rd(K,n,m),rs(s,K);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) rd(h[i][j]);
	}
	init(K);
	for(int i=1;i<=n*m;i++) p[i]=i;
	bool flag=1;
	while(flag){
		memset(st,0,sizeof(st));
		flag=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int x=id(i,j);
				if(find(x)==x&&!st[find(x)]) flag|=!bfs({i,j});
			}
		}
	}
	int ans=0,now=INF;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x=id(i,j);
			if(find(x)==x&&h[i][j]){
				int sz=bfs({i,j});
				if(sz<now) now=sz,ans=sz;
				else if(sz==now) ans+=sz;
			}
		}
	}
	wt('\n',now,ans);
	return 0;
}

总结：

其实感觉这个东西还是比较套路的，就是让你在有传递性的图上求满足最小权值的点，目前我还没有遇到其他利用 boruvka 的思想的题，但是不会这个感觉确实很难想出来（