• 欢迎光临~

ABC 214D Sum of Maximum Weights(并查集模拟删边)

开发技术 开发技术 2022-11-22 次浏览

ABC 214D Sum of Maximum Weights(并查集模拟删边)

Sum of Maximum Weights

​ 给出有 (n;(2 le n le 1e5))个点的一棵树,定义(f(x, y))表示从节点 x 到节点 y 的最短路中的最大边权。

请输出(sum_{i=1}^{N-1} sum_{j=i+1}^{N},f(i, j))

思路:

​ 首先我们可以知道,由于这是一棵树,所以路径是唯一的。那么从 i 到 j 的路径上,只有一个最大的边权会造成贡献,我们就考虑往贡献的方向思考。对于一条边来说,当且仅当这条边为某两个点路径中最大边权的时候,会对答案造成贡献。

​ 我们把通过这条边的所有点分成两个集合,可以发现以这条边为最大边权的那些点具有一个特点:就是在连接该条边使他们联通之前,没有比这个边权值更大的边,这个时候,这条边就会对那些点做出贡献。所以我们就可以从小到大连边,模拟一个删边的过程,也是类似一个最小生成树的过程。

代码

​ 边权从小到大排序,用这条边连接的集合大小乘上边权就是这条边对答案的贡献。

const int N = 100005;

vector<array<int, 3> > vc;
int fa[N];
ll cnt[N];
int n;

int fd(int x)  
{
    if(fa[x] != x)  fa[x] = fd(fa[x]);
    return fa[x];
}

int main()
{
    cin >> n;
    for(int i = 1; i < n; i ++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        vc.push_back({w, u, v});
    }
    for(int i = 1; i <= n; i ++)
        fa[i] = i, cnt[i] = 1;
    sort(all(vc));

    ll res = 0;
    for(auto x : vc)
    {
        int w = x[0], u = x[1], v = x[2];
        int fx = fd(u), fy = fd(v);
        if(fx == fy)    continue;
        res += cnt[fx] * cnt[fy] * w;
        cnt[fy] += cnt[fx];
        fa[fx] = fy;
    }
    cout << res << 'n';
}
程序员灯塔
转载请注明原文链接:ABC 214D Sum of Maximum Weights(并查集模拟删边)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com