有两种方法：一种是先求最小生成树，然后删边；另一种是先把除了节点一以外的连通块分别求出来最小生成树，将每个连通块和节点一连边，然后不断更新答案。

第一种方法的时间复杂度为 $O(n^4)$，第二种方法的时间复杂度为 $O(n^2)$。

解法一 代码

解法二 代码

因为边最多有 $100$ 条，所以有效的节点编号最多只有 $200$ 个，考虑离散化。

设离散化之后的 $P \times P$ 的邻接矩阵 $A$ ，那么不难想到这个邻接矩阵经过两条边的最短路就是 

$\displaystyle B[i, j] = \min_{1 \le k \le P} {A[i, k] + A[k, j]} \notag $

紧接着，经过三条边的最短路也不难想到。

$\displaystyle C[i, j] = \min_{1 \le k \le P} {A[i, k] + B[k, j]} \notag $

联想到什么了吗？像乘法一样！实际上，求经过 $n$ 条边的最短路等价于一个广义“矩阵乘法”，用 $A^m$ 表示经过 $m$ 条边的最短路的话，就能表示出来一般的式子： 

$\displaystyle A^{a + b}[i, j] = \min_{1 \le k \le P} {A^a[i, k] + A^b[k, j]} \notag $

于是，求几条边就相当于求“几次幂”，求幂的话当然是快速幂了。

具体到这个广义的“矩阵乘法”快速幂的话，一次“矩阵乘法”就类似于进行一次 $\mathrm{floyd}$。

这题实际上相当于在一条 $1$ ~ $n$ 的路径，找到两个点 $a, b$（先经过 $a$），使得 $w(b) - w(a)$ 最大。

可以用 SPFA 算法维护从节点 $1$ 到其它节点的点权值的最小值，以及节点 $n$ 到该节点的点权值的最大值，具体实现时候，用 $\min(min(u), w(v))$ 代替 $min(u) + w(v)$ 进行松弛就可以了。

最后枚举所有的节点，找到 $\displaystyle \max_{1 \le i \le n}(max(i) - min(i))$ 。

上述题目实际可以简化为：求一个节点 $1$ 到节点 $n$ 的路径，第 $k + 1$ 大的边权最小。是一个贪心的思想，很容易得出。

我们用 $f[u, k]$ 表示在节点 $1$ 到节点 $u$ 的路径中，用了 $k$ 次免费机会时，路径上最大的边权的最小值。

那么对于一个边 $u \to v$ 有以下状态转移：

1. 当这个边不免费时

   $f[v, k] = \min(f[v, k], \max(f[u][k], w(u, v)))$

2. 当这个边免费时

   $f[v, k + 1] = \min(f[v, k + 1], f[u, k])$

这个状态转移显然有后效性，因为题目给出的并不一定是 DAG，确定不了遍历顺序。对于这种情况，我们使用 SPFA 来进行状态的转移。这样的最短路问题被称为 分层图最短路。用 SPFA 算法的时间复杂度是 $O(tNP)$，其中 $t$ 应该是一个比较小的常数，实际可以 AC 这一题。

（实际上是我比赛时的草稿，可能会有些跳跃，不过总体应该还算清晰）

$y$ 表示扩大后的长减去 $\Delta y$，$x$ 同理

下面是思路：

最小情况： 所有三角形的斜边作为向量相加为对角线(斜边为路线)，则三角形最小时直角顶点为 $ (x_i, y_i) $

相似 => $\displaystyle\frac{y}{\Delta x} = \frac{a_i}{b_i}, \frac{x}{\Delta y} = \frac{b_i}{a_i} $ => $ \displaystyle{ a_i \Delta x + b_i \Delta y = k }$

故 k 的最小值大于等于左式

$ \displaystyle{ a_i \times (x_i - x_{i - 1}) + b_i \times (y_i - y_{i - 1}) \leq k }$

移项，得

$ \displaystyle{ y_i \le \frac{k - a_i \times (x_i - x_{i - 1})}{b_i} + y_{i - 1} }$

观察三角形，易得（画出来的话可能会直观一点） 

$ \displaystyle{ \frac{k}{a_i} \ge \Delta x = x_i - x_{i - 1} \\ \text{于是有} \\ x_{i - 1} \ge x_i - \frac{k}{a_i} }$

又 

$ \displaystyle{ x_i - x_{i - 1} \ge 0 } $

所以 

$ \displaystyle{ x_i \ge x_{i - 1} \ge x_i - \frac{k}{a_i} } $

接下来，由得到的这两组不等式就可以求得答案了，即枚举除定值外的 $i, x_i, x_{i - 1}, k$ 

如果因变量 $y_i$ 大于等于 $m$，就满足题目要求。

具体来说，最外面枚举 $k$，然后枚举积木，横坐标，得到 $y_n$ 的最大值，然后和 $m$ 比较，找到最小的 $k$。

根据上面的描述，不难想到状态表示：$f[i, j]$ 表示枚举到第 $i$ 个积木，横坐标枚举到 $j$ 时纵坐标的最大值，最后和 $m$ 比较的是 $f[n, m]$。

最后，只是简单的枚举其实还不能通过这一题，因为我们并不知道答案的具体取值范围，如果是 $1 \times 10^9$ 的级别，枚举一万年也算不出来，因为我们是要找最小的满足条件的 $k$（大于这个值的都满足条件），所以对于 $k$，我们用二分来找到答案。

最后的时间复杂度应该是 $O(nm^2 \log r) \ (r \text{ 取你取的二分边界})$

这个题只是暴力枚举会超时，考虑优化。

对于行（y 轴），我们用双指针暴力枚举，时间复杂度是 $O(m)$ 。

对于列（x 轴），维护每一列（两个行指针间）的最值，然后用双指针枚举每一列，用单调队列维护两个列指针间的最值信息，求得矩形在 x 轴上的最长长度，然后乘以暴力枚举的 y 轴长度，时间复杂度是 $O(n)$。

最后，整体的时间复杂度是 $O(mn) \ (T(m, n) = 100mn = O(mn))$。