Forsaken喜欢独一无二的树牛客

偏执的太偏执、 2023-06-11 03:12 9阅读 0赞

这个题太秀了

卡自闭队友

蔡哥树剖lca搞

让我心心念念好几天

原来是这么个玩意。

[https://ac.nowcoder.com/acm/contest/1221/H][https_ac.nowcoder.com_acm_contest_1221_H]

题意：给出一个n个点m条边的图，每个边有权值w，你可以删除一些边，使得剩下的边的最小生成树大小不变并且这个图的最小生成树是独一无二的。现在我们想要知道删除的边的权值和最小是多少？

思路：要形成独一无二的最小生成树，那么就没有别的边可以在构造最小生成树时加入最小生成树。

我们可以在计算最小生成树时求所有可以加入最小生成树的边权和，再减去一个最小生成树的边权和就是答案。

#include<bits/stdc++.h>
    using namespace std;
    const int M=2e5+5;
    using ll =long long;
    struct Node{int from,to,w;}e[M];
    bool cmp(const Node &a,const Node &b){return a.w<b.w;}
    int n,m,d[M];
    ll res=0;
    int fa(int x){return d[x]==x?x:d[x]=fa(d[x]);}
    int main(){
        scanf("%d%d",&n,&m);
        for(register int i=0;i<=n;i++)d[i]=i;
        for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].w);
        sort(e+1,e+m+1,cmp);
        for(int j,i=1;i<=m;i++){
            j=i;
            while(j<=m&&e[j].w==e[i].w) j++;
    
            for(int x,y,k=i;k<j;k++){
                x=fa(e[k].from);y=fa(e[k].to);
                if(x!=y)  res+=e[k].w;
            }
    
            for(int x,y,k=i;k<j;k++){
                x=fa(e[k].from);y=fa(e[k].to);
                if(x!=y)  d[x]=y,res-=e[k].w;
            }
        }
        cout<<res<<endl;
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_1221_H]: https://ac.nowcoder.com/acm/contest/1221/H

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关【牛客】二叉树遍历

目录题目解题过程解题代码题目 `题目链接`：[点击进入][Link 1] ![在这里插入图片描述][65be80c4cd0f45eb

约定不等于承诺〃/ 2024年03月23日 13:04/ 0 赞/ 160 阅读

相关 Forsaken喜欢独一无二的树牛客

这个题太秀了卡自闭队友蔡哥树剖lca搞让我心心念念好几天原来是这么个玩意。 [https://ac.nowcoder.com/acm/contest/1221

偏执的太偏执、/ 2023年06月11日 03:12/ 0 赞/ 10 阅读

相关牛客网-对称二叉树

题目描述请实现一个函数，用来判断一棵二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。牛客网OJ连接：[https://www.no

系统管理员/ 2023年03月01日 09:41/ 0 赞/ 58 阅读

相关牛客网-二叉树的镜像

题目描述操作给定的二叉树，将其变换为源二叉树的镜像。输入描述: 二叉树的镜像定义：源二叉树 8 / 6 10 / \\ / 5 7 9 1

曾经终败给现在/ 2023年03月01日 09:40/ 0 赞/ 58 阅读

相关牛客网-树的子结构

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） oj连接： [https://www.nowcoder.com

朱雀/ 2023年03月01日 09:36/ 0 赞/ 115 阅读

相关牛客练习赛1-B-树题解

文章目录题目描述输入描述输出描述输入输出备注算法分析解题代码 --

系统管理员/ 2022年12月28日 12:45/ 0 赞/ 199 阅读

相关平衡二叉树（C++牛客网）

解题思路：（1）依次判断每个结点的左右子树是否满足高度差 class Solution { private: bool tag=true;

清疚/ 2022年11月19日 04:20/ 0 赞/ 232 阅读

相关树的直径（C++牛客网）

解题思路：（1）dfs class Solution { private: int max_sum=0; int end=

快来打我*/ 2022年11月18日 13:55/ 0 赞/ 174 阅读

相关重建二叉树（C++牛客网）

解题思路：（1）注意先序遍历和中序遍历中根结点的位置 / Definition for binary tree struct TreeNo

男娘i/ 2022年11月18日 10:53/ 0 赞/ 196 阅读

相关树——牛客网刷题第二波

发现牛客网很不稳定，刷的是“树”，时不时冒出几个“图”，emmm，对于强迫症的我真是煎熬，还在想要不要把标题改喽——树图~~~~暂时先这样吧~~~~ 1.一棵左右子树均不空

客官°小女子只卖身不卖艺/ 2022年01月26日 01:31/ 0 赞/ 338 阅读