Tarjan算法学习总结 发表于 2018-10-17 一些概念: 强连通图: 如果 在一个有向图G中,每两个点都强连通,我们就叫这个图,强连通图。 强连通分量(strongly connected components):在一个有向图G中,有一个子图,这个子图每2个点都满足强连通,我们就叫这个子图叫做强连通分量。 割点:一个结点称为割点(或者割顶)当且仅当去掉该节点极其相关的边之后的子图不连通。 桥:一条边称为桥(或者割边)当且仅当去掉该边之后的子图不连通。 dfn[]:保存这个点被第几次搜到。 low[]:保存这个点在或其子树能够追溯到的最早的栈中节点的次序号。 阅读全文 »
【货车运输】 发表于 2018-10-16 作者认为这是一道非常好的题目,既包含了生成树,又包含了求lca以及倍增的思想 进入正题: 容易想到为了让火车最大载重尽量大,我们需要把原图变为它的最大生成树。接下来每次询问两点我们只需要求其简单路径上的边权最小值即可。 阅读全文 »
【SCOI2005】互不侵犯 发表于 2018-07-21 题目描述在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 ( 1 <=N <=9, 0 <= K <= N * N) 阅读全文 »