RainAir's Blog
  • Activity Calendar

    Loading...

    Radar Chart

    Loading...

    Release Chart

    Loading...

    Classification Chart

    Loading...

    Tag Chart

    Loading...

  • New thing
    New thing
RainAir
  • Good afternoon, it 's time to take a nap

  • Navigation
  • Home
  • 归档
  • 关于
  • Links
  • 留言板
  • ROJ
Admin
Post
Comment

Articles under the label of 最小树形图

  1. Home
  2. 最小树形图

最小树形图 / 朱刘算法

前置定义树形图:在一个有向图中,满足存在一个入度为 $0$ 的点,除了该点入读均为 $1$,且该图不存在环,那么称为树形图。 最小树形图:给定有向边权图,求以某点为根的边权和最小的子图,满足该子图为树形图。朱刘算法模板链接 相当于是一种贪心的思想。 首先我们发现一个合法的树形图中除根外的每个点只有一条入边,所以我们就贪心的选择原图中所有入边中最小的。但是注意到这样选出来的子图可能会存在环,所...

  • RainAir
  • January 20, 2019
  • 1 comments
    • Popular articles
    • Latest comments
    • Random articles
    Popular articles
    • I'm back

      浏览次数: 12649
    • NOI2021 退役记

      浏览次数: 10037
    • SDOI2020 退役记

      浏览次数: 8394
    • 点双连通分量 & 圆方树学习笔记

      浏览次数: 6908
    • CSP2019 游记

      浏览次数: 6131
    Latest comments
    • gxy
      Orz
    • gxy
      Orz
    • gxy
      Orz
    • starback
      orzwyh!
    • Tnuzy_plzro
      Orz
    Random articles
    • 「NOIP2016」换教室

      浏览次数: 1361
    • 「CF1097G」Vladislav and a Great Legend

      浏览次数: 1455
    • AGC038 部分题解

      浏览次数: 1470
    • 「数学基础」莫比乌斯反演

      浏览次数: 3411
    • ARC119F AtCoder Express 3

      浏览次数: 1444
    Blog Info
    • 299Posts Num
    • 169Comments Num
    • 7 Y 142 DOperating Days
    • 2 Years AgoLast activity
    广告

    N O I 2 0 2 1 倒 计 时

    -1414 天 -5 时 -40 分 -8 秒
    Tag cloud
    数位 dp 动态规划 计数 构造 线段树 网络流 数论 贪心 二分图 二分答案 数学 最短路 字符串 计算几何 多项式 平衡树 树状数组 树链剖分 拓扑排序 LCT 分块 容斥 Counting 数据结构 adhoc LCA 博弈论 最小生成树 强连通分量 数学期望
    Article Directory
    Powered by Typecho | Theme by handsome © 2025 Copyright | 鲁ICP备18045443号-1