新的做法

最短路为 MST 上一条边的结论别的题解已经证明了，这里不再赘述
有这么一个结论：在 Kruskal 算法合并

u,v

两个点时，你可以连

u

所在连通分量和

v

所在连通分量任意两个点
证明：连边有两个用，一是将两个连通分量连起来，二是有权值
第一个作用显然不影响，这里考虑第二个
如果要用到

(u,v)

边的权值，则由 Kruskal 算法的性质，

u,v

子树的所有边两端颜色都相同
所以

u

所在连通分量每个点颜色相同，

v

同理
此时连哪两个点都一样了

所以直接合并时连接两个子树的任一度数不大于

1

的点
由数学归纳法，合并后子树永远是一条链，用一个数组维护链的端点即可

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=4e5+5;
int n,m,k,q,fa[N],col[N],lst[N];
vector<pair<int,int> >G[N];
multiset<int>ans;
struct edge{
	int u,v,w;
	bool operator<(edge b){
		return w<b.w;
	}
}e[M];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	cin>>n>>m>>k>>q;
	for(int i=1,u,v,w;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+m+1);
	for(int i=1;i<=n;i++)cin>>col[i],fa[i]=lst[i]=i;
	for(int i=1;i<=m;i++){
		auto[u,v,w]=e[i];
		int fu=find(u),fv=find(v);
		if(fu==fv)continue;
		fa[fu]=fv;
		G[lst[fu]].push_back({lst[fv],w});
		G[lst[fv]].push_back({lst[fu],w});
		lst[fv]=fu;
	}
	for(int u=1;u<=n;u++)
		for(auto[v,w]:G[u])
			if(u<v&&col[u]!=col[v]) ans.insert(w);
	while(q--){
		int u,k;cin>>u>>k;
		for(auto [v,w]:G[u])
			if(col[u]==col[v]&&k!=col[v]) ans.insert(w);
			else if(col[u]!=col[v]&&k==col[v])ans.erase(ans.find(w));
		printf("%d\n",*ans.begin());
		col[u]=k;
	} 
	return 0;
}

文章操作

相关推荐

评论

新的做法