P4234 最小差值生成树

    • 382通过
    • 1.6K提交
  • 题目提供者 fstqwq 管理员
  • 评测方式 云端评测
  • 标签 Link-Cut Tree,LCT 图论 枚举,暴力 深度优先搜索,DFS 生成树 O2优化
  • 难度 省选/NOI-
  • 时空限制 3000ms / 262MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个标号为从 $1$ 到 $n$ 的、有 $m$ 条边的无向图,求边权最大值与最小值的差值最小的生成树。

    输入输出格式

    输入格式:

    第一行两个数 $n, m$,表示图的点和边的数量。

    第二行起 $m$ 行,每行形如 $u_i, v_i, w_i$,代表 $u_i$ 到 $v_i$ 间有一条长为 $w_i$ 的无向边。

    输出格式:

    输出一行一个整数,代表你的答案。

    数据保证存在至少一棵生成树。

    输入输出样例

    输入样例#1: 复制
    4 6 
    1 2 10 
    1 3 100 
    1 4 90 
    2 3 20 
    2 4 80 
    3 4 40 
    输出样例#1: 复制
    20

    说明

    对于 30% 的数据,满足 $1 \leq n \leq 100, 1 \leq m \leq 1000$

    对于 97% 的数据,满足 $1 \leq n \leq 500, 1 \leq m \leq 100000$

    对于 100% 的数据,满足 $1 \leq n \leq 50000, 1 \leq m \leq 200000, 1 \leq w_i \leq 10000$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。