发表于

一些概念：

  1. 强连通图： 如果 在一个有向图G中，每两个点都强连通，我们就叫这个图，强连通图。
  2. 强连通分量(strongly connected components)：在一个有向图G中，有一个子图，这个子图每2个点都满足强连通，我们就叫这个子图叫做强连通分量。
  3. 割点：一个结点称为割点（或者割顶）当且仅当去掉该节点极其相关的边之后的子图不连通。
  4. 桥：一条边称为桥（或者割边）当且仅当去掉该边之后的子图不连通。
  5. dfn[]：保存这个点被第几次搜到。
  6. low[]：保存这个点在或其子树能够追溯到的最早的栈中节点的次序号。
阅读全文 »

发表于

作者认为这是一道非常好的题目，既包含了生成树，又包含了求lca以及倍增的思想

进入正题：

容易想到为了让火车最大载重尽量大，我们需要把原图变为它的最大生成树。接下来每次询问两点我们只需要求其简单路径上的边权最小值即可。

阅读全文 »

发表于

题目描述

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 （ 1 <=N <=9, 0 <= K <= N * N）

阅读全文 »

发表于

思路如下

首先先写一个函数判断两个洞是否相连，即两洞之间距离是否小于等于球直径（注意是直径）。

阅读全文 »