[BZOJ] 1631: [Usaco2007 Feb]Cow Party

好的，这是一道关于牛的题目，它描述了一群牛要去参加一个聚会，它们之间有一些道路相连，每条道路都有一个不同的长度。在聚会上，每头牛都要喝一杯牛奶，而且它们的喝牛奶的速度不同，因此有些牛会在其他牛之前到达聚会现场。现在你需要计算出所有牛到达聚会现场所需要的时间，并找出其中最长的那个时间，也就是说，如果所有牛同时出发，最后到达聚会现场的牛需要的时间是多少，而且这个时间要尽量短。

具体来说，题目给出了一个图，其中每个节点表示一头牛，每条边表示两头牛之间的道路，每条边都有一个长度，表示走过这条道路所需要的时间。同时，题目还给出了每头牛喝一杯牛奶所需要的时间。你需要计算出所有牛到达聚会现场所需要的时间，并找出其中最长的那个时间。

这道题可以使用 Dijkstra 算法求解，具体的算法过程可以参考下面的代码：

相关问题

【BZOJ 3445】【Usaco2014 Feb】Roadblock

题目描述

牛牛和她的朋友们正在玩一个有趣的游戏，他们需要构建一个有 $n$ 个节点的无向图，每个节点都有一个唯一的编号并且编号从 $1$ 到 $n$。他们需要从节点 $1$ 到节点 $n$ 找到一条最短路径，其中路径长度是经过的边权的和。为了让游戏更有趣，他们决定在图上添加一些额外的边，这些边的权值都是 $x$。他们想知道，如果他们添加的边数尽可能少，最短路径的长度最多会增加多少。

输入格式

第一行包含两个正整数 $n$ 和 $m$，表示节点数和边数。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示一条无向边 $(u_i,v_i)$，权值为 $w_i$。

输出格式

输出一个整数，表示最短路径的长度最多会增加多少。

数据范围

$2 \leq n \leq 200$

$1 \leq m \leq n(n-1)/2$

$1 \leq w_i \leq 10^6$

输入样例 #1：

4 4
1 2 2
2 3 3
3 4 4
4 1 5

输出样例 #1：

5

输入样例 #2：

4 3
1 2 1
2 3 2
3 4 3

输出样例 #2：

2

算法

(BFS+最短路) $O(n^3)$

我们把问题转化一下，假设原图中没有添加边，所求的就是点 $1$ 到点 $n$ 的最短路，并且我们已经求出了这个最短路的长度 $dis$。

接下来我们从小到大枚举边权 $x$，每次将 $x$ 加入图中，然后再次求解点 $1$ 到点 $n$ 的最短路 $dis'$，那么增加的最短路长度就是 $dis'-dis$。

我们发现，每次加入一个边都需要重新求解最短路。如果我们使用 Dijkstra 算法的话，每次加入一条边需要 $O(m\log m)$ 的时间复杂度，总的时间复杂度就是 $O(m^2\log m)$，无法通过本题。因此我们需要使用更优秀的算法。

观察到 $n$ 的范围比较小，我们可以考虑使用 BFS 求解最短路。如果边权均为 $1$，那么 BFS 可以在 $O(m)$ 的时间复杂度内求解最短路。那么如果我们只是加入了一条边的话，我们可以将边权为 $x$ 的边看做 $x$ 条边的组合，每次加入该边时，我们就在原始图上添加 $x$ 条边，边权均为 $1$。这样，我们就可以使用一次 BFS 求解最短路了。

但是，我们不得不考虑加入多条边的情况。如果我们还是将边权为 $x$ 的边看做 $x$ 条边的组合，那么我们就需要加入 $x$ 条边，而不是一条边。这样，我们就不能使用 BFS 了。

但是，我们可以使用 Floyd 算法。事实上，我们每次加入边时，只有边权等于 $x$ 的边会发生变化。因此，如果我们枚举边权 $x$ 时，每次只需要将边权等于 $x$ 的边加入图中，然后使用 Floyd 算法重新计算最短路即可。由于 Floyd 算法的时间复杂度为 $O(n^3)$，因此总的时间复杂度为 $O(n^4)$。

时间复杂度

$O(n^4)$

空间复杂度

$O(n^2)$

C++ 代码

注意点：Floyd算法计算任意两点之间的最短路径，只需要在之前的路径基础上加入新的边构成的新路径进行更新即可。

BZOJ2194: 快速傅立叶之二 (FFT)

这是一道经典的FFT模板题目，需要你掌握FFT的基本原理和实现。

FFT（快速傅里叶变换）是一种用于计算离散傅里叶变换（DFT）的算法。它将DFT的时间复杂度从O(N^2)降低到了O(N*logN)，因此在处理大规模数据时具有很高的效率。

对于这道题目，你需要计算两个多项式的乘积。可以将这两个多项式看作是两个长度为N的序列A和B，然后使用FFT算法计算它们的卷积，即C[i] = A[i]*B[i]，最后再使用逆FFT将C转化为多项式形式即可。

具体实现方面，可以使用递归实现FFT算法，也可以使用迭代实现。递归实现的代码比较简洁，但在处理大规模数据时可能会出现栈溢出的问题。迭代实现则可以避免这种问题，但代码会稍微复杂一些。

如果你还没有掌握FFT的基本原理和实现，建议先去学习一下。推荐的学习资源包括CLRS算法书籍、博客文章和相关视频教程。