Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. Tarjan 割点学习笔记

    在一个无向图中,如果删掉点 v v 后图的连通块数量增加,则称点 v v 为图的割点

    于  Tarjan, 割点, 图论, 学习笔记, 算法模板 继续阅读

  2. 「NOI2016」网格 - 图连通性

    在一个 n×m n \times m 的网格上,有 c c 个障碍,其余均为空地。求至少需要将多少空地转化为障碍,可以使得存在两个空地在四连通意义下不在同一连通块中。

    于  BZOJ, NOI, Tarjan, 割点, 图论 继续阅读

  3. 「POI2008」BLO - 割点

    Byteotia 城市有 n n 个 towns,m m 条双向 roads。每条 road 连接两个不同的 towns,没有重复的 road。所有 towns 连通。

    求当把每个点封锁时,会有多少有序点对 (u,v) (u, v) 不连通。

    于  BZOJ, POI, Tarjan, 割点, 图论 继续阅读

  4. 「HNOI2012」矿场搭建 - 割点

    煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。

    请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。

    于  BZOJ, HNOI, Tarjan, 割点, 图论 继续阅读