不知道哪天晚上的 ABC D 题解
2026-08-09 12:03:26
发布于：浙江
16阅读
0回复
0点赞
[ABC214D] Sum of Maximum Weights
先看题，就是求任意两点边权的最大值之和，考虑暴力。
真的有人考虑吗不难发现，这个时间复杂度是B/DFS的单次 乘上查询的 ， 复杂度必爆，考虑优化。
不难发现可以使用贡献法（是不是星原讲了所以发现了），算每条边会变成多少点对的最大边权的边，如果这条边边权是 ，有 个点对，那么这条边的总贡献就是 ，这里沿用MST的思想，将边权从小到大排序便于计算，在MST里的Kruskal算法中，想象每个点就是一个连通块，不断连边减小连通块。
当我们加入 边时，这条边连接 两块，由于按边权排序，两个连通块内部的边边权必然是小于 的，如果一个来自 的点要到 去，那必须经过这条边，又因为当前边是目前最大边权的边，所以 就是路径上权值最大的边，跨 的点对 ，那么 的贡献就是 ，这样统计不重不漏，时间复杂度 ，于是得到以下代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace syh;
struct edge
{
int u, v, w;
bool operator<(const edge &b) const
{
return w<b.w;
}
};
vector<edge> g;
int fa[100005];
long long lt[100005];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n;
long long ans=0;
cin>>n;
for(int i = 1;i<=n;i++) fa[i]=i,lt[i]=1;
for(int i = 1;i<n;i++)
{
int u, v, w;
cin>>u>>v>>w;
g.push_back({u,v,w});
}
sort(g.begin(),g.end());
for(auto &e:g)
{
int u=e.u, v=e.v, w=e.w;
if(find(u)!=find(v))
{
ans+=1LL*w*lt[find(u)]*lt[find(v)];
fa[find(v)]=find(u);
lt[find(u)]+=lt[find(v)];
}
}
cout<<ans;
}
然后就得到了
调代码时，发现重复调用 函数会破坏原来的根，所以用变量来储存值，直接用。
AC CODE
#include <iostream>
#include <vector>
#include <algorithm>
using namespace syh;
struct edge
{
int u, v, w;
bool operator<(const edge &b) const
{
return w<b.w;
}
};
vector<edge> g;
int fa[100005];
long long lt[100005];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n;
long long ans=0;
cin>>n;
for(int i = 1;i<=n;i++) fa[i]=i,lt[i]=1;
for(int i = 1;i<n;i++)
{
int u, v, w;
cin>>u>>v>>w;
g.push_back({u,v,w});
}
sort(g.begin(),g.end());
for(auto &e:g)
{
int u=e.u, v=e.v, w=e.w;
int nu=find(u), nv=find(v);
if(nu!=nv)
{
ans+=1LL*w*lt[nu]*lt[nv];
fa[nv]=nu;
lt[nu]+=lt[nv];
}
}
cout<<ans;
}
绿++但是洛谷交不了。
有帮助，赞一个