• 周三. 6月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【ABC 214D】Sum of Maxinum Weights

admin

11月 28, 2021

简析

对于每个 (i,(1≤i<N)),我们将计算使 (f(u,v)=w_i) 的总数目 ((u,v))。当且仅当连接顶点 (u)(v) 的路径包含边 (i) 且路径中任何其他边的权值都小于 (w_i) 时,(f(u,v)=w_i) 成立。

一个只包含权重小于 (w_i)​ 的边的图形成了一个森林,而 (u_i)​ 和 (v_i)​ 总是属于不同的连通分量。当且仅当 (u)​ 属于其中一个连接组件,(v)​ 属于另一个连接组件时,(f(u,v)=w_i) 成立。

因此,可以通过将边按权值递增的顺序添加到图中,并通过并查集这样的数据结构获取连通块的大小来解决这个问题。

(译自官方题解,略有改动)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,dis[N],fa[N],siz[N];
int getf(int x) {
	if(x^fa[x]) {
		return fa[x]=getf(fa[x]);
	}
	return x;
}
void merge(int x,int y) {
	x=getf(x),y=getf(y);
	if(x==y) {
		return ;
	}
	if(siz[x]<siz[y]) {
		fa[x]=y,siz[y]+=siz[x];
	} else {
		fa[y]=x,siz[x]+=siz[y];
	}
}
struct edge {
	int u,v,w;
	edge() {}
	edge(int x,int y,int z) {
		u=x,v=y,w=z;
	}
};
bool operator<(edge x,edge y) {
	return x.w<y.w;
}
vector<edge> v;
int main() {
	scanf("%d",&n);
	for(int i=1,x,y,z; i<n; i++) {
		scanf("%d %d %d",&x,&y,&z),v.push_back(edge(x,y,z));
	}
	for(int i=1; i<=n; i++) {
		fa[i]=i,siz[i]=1;
	}
	sort(v.begin(),v.end());
	long long ans=0;
	for(auto i:v) {
		int u=getf(i.u),v=getf(i.v),w=i.w;
		ans+=(long long)w*siz[u]*siz[v],merge(u,v);
	}
	printf("%lld",ans);
	return 0;
}

知识共享许可协议

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

限于本人水平,如果文章有表述不当之处,还请不吝赐教。

发表评论

您的电子邮箱地址不会被公开。