AtCoder Beginner Contest 355（F - MST Query）

很久没有见到这么好的题了。

原题面

用 C h a t G P T − 4 o ChatGPT-4o ChatGPT−4o翻译好的题面：

你被给定一个带权无向连通图 G G G，它有 N N N 个顶点和 N − 1 N-1 N−1 条边，顶点编号为 1 1 1 到 N N N，边编号为 1 1 1 到 N − 1 N-1 N−1。边 i i i 连接顶点 a i a_i ai​ 和 b i b_i bi​，权重为 c i c_i ci​。

给定 Q Q Q 个查询需要顺序处理。第 i i i 个查询描述如下：

给定整数 u i , v i , w i u_i, v_i, w_i ui​,vi​,wi​。在 G G G 中添加一条权重为 w i w_i wi​ 的边连接顶点 u i u_i ui​ 和 v i v_i vi​。然后，打印 G G G 的最小生成树的边权和。

约束条件

• 2 ≤ N ≤ 2 × 1 0 5 2 \leq N \leq 2 \times 10^5 2≤N≤2×105
• 1 ≤ Q ≤ 2 × 1 0 5 1 \leq Q \leq 2 \times 10^5 1≤Q≤2×105
• 1 ≤ a i < b i ≤ N 1 \leq a_i < b_i \leq N 1≤ai​<bi​≤N
• 1 ≤ u i < v i ≤ N 1 \leq u_i < v_i \leq N 1≤ui​<vi​≤N
• 1 ≤ c i , w i ≤ 10 1 \leq c_i, w_i \leq 10 1≤ci​,wi​≤10

图在处理查询之前是连通的。

所有输入值均为整数。

建议还是到原题面看看样例的图。

讲解

通过数据范围发现所有边的边权都在 10 10 10 以内，那么就尝试以边权为突破口。

这里有一个显著结论：

• 当只考虑边权为 1 1 1 的边时，如果加入这条边没有形成环。那么这条边一定会一直在 M S T （最小生成树） MST（最小生成树） MST（最小生成树） 里。

接下来考虑边权只有 1 1 1 和 2 2 2 的情况（按照边出现的时间顺序考虑）。

如果当前的边的边权为 1 1 1 ，且在只考虑边权为 1 1 1 的边时加入当前边不构成环，但在考虑边权有 1 1 1 和 2 2 2 的情况下加入当前边构成环，说明这条边最终在MST中，而且还替代掉了一个边权为 2 2 2 的边。

我也知道抽象，所以来看图。

假设有三个点，三条边：

格式：端点1 \quad 端点2 \quad 边权

第一条： 1 2 1 1 \quad 2 \quad 1 121

第二条： 2 3 2 2 \quad 3 \quad 2 232

第三条： 1 3 1 1 \quad 3 \quad 1 131

如果我们只考虑边权为 1 1 1 的边，那么图是这样的（没有画第二条边）：

如果我们考虑边权为 1 1 1 和 2 2 2 的边，那么图是这样的：

在尝试插入第三条边的时候会发现如果插入这条边就会有环，所以要替代掉第二条边，在代码实现的时候在这里记录一下：有一条边权为 2 2 2 的边变为了边权为 1 1 1 的边，最后输出答案的时候做一下前缀和就行了。

对于其他边权的边也同理。

其中 f l a g flag flag 用来判断上一轮结束的时候这条边有没有在 M S T （最小生成树） MST（最小生成树） MST（最小生成树） 中。

配合 D S U （并查集） DSU（并查集） DSU（并查集） 写出代码，还有一些没有将的放到代码注释里了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[400005],b[400005],c[400005],fas[200005],flag[400005],dp[400005];
inline ll fid(ll p){
	if(p!=fas[p])fas[p]=fid(fas[p]);
	return fas[p];
}
inline void miker(ll x,ll y){
	x=fid(x);y=fid(y);
	fas[x]=y;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(ll i=1;i<n+m;i++)cin>>a[i]>>b[i]>>c[i];
	for(ll q=1;q<=10;q++){
		for(ll i=1;i<=n;i++)fas[i]=i;
		for(ll i=1;i<n+m;i++){
			if(c[i]>q)continue;
			if(fid(a[i])!=fid(b[i])){
				miker(a[i],b[i]);
				if(!flag[i]){
					dp[i]+=q;
					flag[i]=1;
				}
			}
			else if(flag[i]){
				// 为什么替代调的边的边权一定是 q ，因为在之前的循环中已经把 边权<q 的边能替换的都替换掉了。 
				dp[i]-=q;
				
				// 因为后面要求前缀和，所以这里要把 flag 变为 0 ，否则会重复计算。 
				flag[i]=0;
			}
		}
	}
	ll ans=0;
	for(ll i=1;i<n+m;i++){
		ans+=dp[i];
		if(i>=n)cout<<ans<<endl;
	}
	return 0;
}

总结方法

1. 在做题是可以考虑通过数据范围寻找突破口。

2. 在动态加边的题中可以考虑用前缀和。

最后，希望大家可以把不懂的地方在评论区或私信说出来，也希望可以指出我的错误。我会尽量在12小时内回答。

求点赞、关注、收藏。