Menci

眉眼如初,岁月如故

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


  1. 「HNOI2005」狡猾的商人 - 差分约束

    刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了 n n 个月以来的收入情况,其中第 i i 个月的收入额为 Ai A_i 。当 Ai A_i 大于 0 0 时表示这个月盈利 Ai A_i 元,当 Ai A_i 小于 0 0 时表示这个月亏损 Ai A_i 元。所谓一段时间内的总收入,就是这段时间内每个月的收入额的总和。刁姹的任务是秘密进行的,为了调查商人的账本,她只好跑到商人那里打工。她趁商人不在时去偷看账本,可是她无法将账本偷出来,每次偷看账本时她都只能看某段时间内账本上记录的收入情况,并且她只能记住这段时间内的总收入。现在,刁姹总共偷看了 m m 次账本,当然也就记住了 m m 段时间内的总收入,你的任务是根据记住的这些信息来判断账本是不是假的。

    于  BZOJ, HNOI, 图论, 差分约束 继续阅读

  2. 欧拉回路学习笔记

    若图 G G 中存在这样一个环,使得 G G 中每条边都恰好在环上出现一次,则称为欧拉回路。

    具有欧拉回路的图称为欧拉图。

    于  图论, 学习笔记, 欧拉回路, 算法模板 继续阅读

  3. 「BZOJ 1718」Redundant Paths - 割边

    给一个无向连通图,求至少加多少条边使得每两个点之间都存在至少两条路径,即使图没有割边。

    于  BZOJ, USACO, 割边, 图论 继续阅读

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

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

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

  5. Tarjan 割点学习笔记

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

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

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

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

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

  7. 「POI2008」BLO - 割点

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

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

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

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

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

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

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

  9. 「NOI2006」最大获利 - 最大权闭合图

    在前期市场调查和站址勘测之后,公司得到了一共 N N 个可以作为通讯信号中转站的地址,建立第 i i 个通讯中转站需要的成本为 Pi Pi )。另外公司调查得出了所有期望中的用户群,一共 M M 个。关于第 i i 个用户群的信息概括为 Ai Ai , Bi Bi Ci Ci :这些用户会使用中转站 Ai Ai 和中转站 Bi Bi 进行通讯,公司可以获益 Ci Ci 。( )公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?

    于  BZOJ, CodeVS, Dinic, NOI, 图论, 最大权闭合图, 最小割, 网络流 继续阅读

  10. 「SCOI2007」修车 - 费用流

    同一时刻有 N N 位车主带着他们的爱车来到了汽车维修中心。维修中心共有 M M 位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这 M M 位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。

    顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

    于  BZOJ, CodeVS, Edmonds-Karp, SCOI, 图论, 网络流, 费用流 继续阅读