Menci

眉眼如初,岁月如故

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


  1. 「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, 强连通分量, 缩点 继续阅读

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

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

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

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

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

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

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

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

  4. 「APIO2009」抢掠计划 - 强连通分量

    城中的道路都是单向的。不同的道路由路口连接。在每个路口都设立了一个 ATM 取款机。酒吧也都设在路口,虽然并不是每个路口都设有酒吧。他将从市中心出发,沿着单向道路行驶,抢劫所有他途径的 ATM 机,最终他将在一个酒吧庆祝他的胜利。

    他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机里面就不会再有钱了。

    于  APIO, BZOJ, Bellman-Ford, DAG, Tarjan, 强连通分量, 最长路, 缩点 继续阅读

  5. 「SCOI2011」糖果 - 强连通分量 + 拓扑排序

    幼儿园里有 N N 个小朋友,老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。在分配糖果的时候,需要满足小朋友们的 K K 个要求。幼儿园的糖果总是有限的,想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

    于  BZOJ, SCOI, Tarjan, 差分约束系统, 强连通分量, 拓扑排序, 缩点 继续阅读

  6. 「HAOI2006」受欢迎的牛 - 强连通分量

    每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N N 头牛,给你 M M 对整数 (A,B) (A,B) ,表示牛 A A 认为牛 B B 受欢迎。 这种关系是具有传递性的,如果 A A 认为 B B 受欢迎,B B 认为 C C 受欢迎,那么牛 A A 也认为牛 C C 受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

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

  7. 「CodeVS 2822」爱在心中 - 强连通分量

    在爱的国度里有 N 个人,在他们的心中都有着一个爱的名单,上面记载着他所爱的人(不会出现自爱的情况)。爱是具有传递性的,即如果 A 爱 B,B 爱 C,则 A 也爱 C。

    如果有这样一部分人,他们彼此都相爱,则他们就超越了一切的限制,用集体的爱化身成为一个爱心天使。现在,我们想知道在这个爱的国度里会出现多少爱心天使。而且,如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的,否则输出 -1。

    于  CodeVS, Tarjan, 图论, 强连通分量, 缩点 继续阅读

  8. Tarjan 强连通分量学习笔记

    在一个有向图中,如果某两点间都有互相到达的路径,那么称中两个点强连通,如果任意两点都强连通,那么称这个图为强连通图;一个有向图的极大强连通子图称为强连通分量

    Tarjan 算法可以在 O(n+m) O(n + m) 的时间内求出一个图的所有强连通分量。

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