# 练习
## abc309_d
题目转化为：
- 有两个连通块，包含的点的编号分别为 $1 \sim N_1, N_1 + 1 \sim N_1 + N_2$
- 定义 $dis_{x, y}$ 表示点 $(x, y)$ 的距离
- 找出两个点 $u, v$，使得 $1 \le u \le N_1, N_1 + 1 \le v \le N_1 + N_2$ 并且 $dis_{1, u} + 1 + dis_{v, N_1 + N_2}$ 最小。
对于 $dis_{1, u}$，我们可以从点 $1$ 进行 BFS 求解；对于 $dis_{v, N_1 + N_2}$，由于题目给出的是无向图，我们可以从点 $N_1 + N_2$ 进行 BFS 求解。分别找到两项的最大值即可。
如果是有向图该如何求解？
## abc272_d
如果在 BFS 的过程中，对于当前格子 $(i, j)$，如果我们暴力枚举 $(k, l)$ 再根据距离是否为 $\sqrt{M}$ 来决定是否转移，那么时间复杂度会超时，计算如下：
- 有 $O(N^2)$ 个格子，每个格子需要花 $O(N^2)$ 时间枚举转移，总时间复杂度 $O(N^4)$。
我们重新将距离的约束条件写一下（这里避免了浮点数运算）：
$
(i - k) ^ 2 + (j - l) ^ 2 = M
$
这是一个 $i, j$ 已知、$k, l$ 未知的二元方程，实际上我们只需要枚举其中一个未知数就能求解出另一个未知数（前提是有解）。
$
j - l = \pm \sqrt{M - (i - k)^2}
$
只需要枚举一个未知数，时间复杂度降低为 $O(N^3)$
我们还可以这样看，$(i - k)$ 和 $(j - l)$ 是位移量 $\Delta x, \Delta y$（因为位移有方向所以 $\Delta x, \Delta y$ 的值可带正负号），我们可以一开始通过枚举预处理出所有符合约束条件的位移量组 $(\Delta x, \Delta y)$，然后在转移时枚举这些位移量组（也就是通俗意义上的方向数组）即可。由于符合条件的位移量最多只有 $O(N)$ 组，因此总时间复杂度依然为 $O(N^3)$。
- 请证明符合条件的位移量最多只有 $O(N)$ 组。
## abc289_e
本题的重点在于状态和转移上。
状态：$(u, v, step)$ 表示经过 $step$ 次移动，高桥在 $u$，青木在 $v$。
我们使用邻接表记录无向图，然后使用 BFS 做一个看上去和暴力的转移：
- 起始状态是 $(1, n, 0)$，目标是最小化 $(n, 1, step)$ 中的 $step$
- $(u, v, step) \to (u', v', step + 1)$，其中 $u', v'$ 分别是与 $u, v$ 相邻的点，且两点颜色不同
- 我们使用双重循环枚举邻接表中 $u, v$ 的邻点 $u', v'$
遍历所有状态是 $O(N^2)$ 的。而总转移的时间则需要对于每个状态的转移时间求和计算，如下，其中 $deg_i$ 表示点 $i$ 的度数：
$
\begin{align}
\sum \limits_{x = 1}^n \sum \limits_{y = 1}^n deg_x \times deg_y &= \sum \limits_{x = 1}^n (deg_x \times \sum \limits_{y = 1}^n deg_y) \\
&= \sum \limits_{x = 1}^n deg_x \times 2M \\
&= 2M \times \sum \limits_{x = 1}^n deg_x \\
&= 4M^2 \\
&= O(M^2)
\end{align}
$
因此，BFS 的总时间复杂度为 $O(N^2 + M^2)$。
## 洛谷 P2296 寻找道路
## 洛谷 P5663 加工零件
## 洛谷 P1144 最短路计数
原图上的所有边在 BFS 过程中有三种情况：
- I 类边：BFS 树上的边
- II 类边：不在 BFS 树上但是连接同层内的点的边
- III 类边：不在 BFS 树上但是连接相邻两层的点的边
- 不会出现跨越两层及以上的边
- I、III 类边都是连接相邻两层的点的边
只有 I、III 类边会对最短路径方案数做贡献。我们可以在 BFS 转移过程中找到 I、III 类边并进行 DP，边转移边累加方案数即可。
```cpp
for (int v : g[u]) {
if (dis[v] == -1) {
dis[v] = dis[u] + 1;
ans[u] = ans[v];
que.push({v, dis[v]});
} else if (dis[v] == dis[u] + 1) {
ans[u] += ans[v];
}
}
```
可以证明，如果将 I 类边和 III 类边建一个有向图，每条边的方向为 $dis$ 小的点连向 $dis$ 大的点，那么这个有向图为有向无环图。因此 DP 是正确的。
## 洛谷 P4663 Switch the Lamp On
按题意模拟地做一个 0-1 BFS 即可。