Menci

眉眼如初,岁月如故

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


  1. Tarjan 点双连通分量学习笔记

    点双连通分量是一个极大的子图,满足图中删去任何一个点都不会改变图的连通性。

    于  Tarjan, 双连通分量, 图论, 学习笔记, 算法模板 继续阅读

  2. 「SHOI2008」仙人掌图 - 仙人掌 DP

    求仙人掌图的直径。

    于  BZOJ, DP, SHOI, Tarjan, 仙人掌 继续阅读

  3. 「IOI2008」岛屿 - 基环树 DP

    给一个由多个基环树构成的图,求所有基环树最长链之和。

    于  BZOJ, DP, SHOI, Tarjan, 基环树 继续阅读

  4. Tarjan 割点学习笔记

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

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

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

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

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

  6. 「POI2008」BLO - 割点

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

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

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

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

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

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

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

  8. 「ZJOI2007」最大半连通子图 - 强连通分量

    一个有向图 G=(V,E) G = (V, E) 称为半连通的(Semi-Connected),如果满足:

    u,vV \forall u, v \in V ,满足 uv u \rightarrow v vu v \rightarrow u ,即对于图中任意两点 u u v v ,存在一条 u u v v 的有向路径或者从 v v u u 的有向路径。

    G=(V,E) G' = (V', E') 满足 VV V' \subseteq V E E' E E 中所有跟 V V' 有关的边,则称 G G' G G 的一个导出子图。
    G G' G G 的导出子图,且 G G' 半连通,则称 G G' G G 的半连通子图。
    G G' G G 所有半连通子图中包含节点数最多的,则称 G G' G G 的最大半连通子图。

    给定一个有向图 G G ,请求出 G G 的最大半连通子图拥有的节点数 K K ,以及不同的最大半连通子图的数目 C C 。由于 C C 可能比较大,仅要求输出 C C X X 的余数。

    于  BZOJ, DP, Tarjan, ZJOI, 强连通分量, 缩点 继续阅读

  9. 「BZOJ 2438」杀人游戏 - 强连通分量

    一位杀手潜入假装成平民。警察希望能在 N N 个人里面,查出谁是杀手。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的人,谁是杀手,谁是平民。假如查证的对象是杀手,杀手将会把警察干掉。

    现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。

    根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?

    于  BZOJ, Tarjan, 强连通分量, 缩点 继续阅读

  10. 用 std::stack 实现非递归 DFS

    众所周知,在有些省份(比如山东、河南),省选时使用 Windows 垃圾系统评测,而 Windows 下默认的系统栈非常小(只有 1M),这造成了有些 DFS 相关算法无法通过极端数据,而是发生『栈溢出』的错误。一种解决方法是使用非递归的 DFS。

    于  DFS, STL, Tarjan, 强连通分量, 树链剖分, 算法模板 继续阅读