[BZOJ] 1631: [Usaco2007 Feb]Cow Party
时间: 2023-08-17 07:03:39 浏览: 74
好的,这是一道关于牛的题目,它描述了一群牛要去参加一个聚会,它们之间有一些道路相连,每条道路都有一个不同的长度。在聚会上,每头牛都要喝一杯牛奶,而且它们的喝牛奶的速度不同,因此有些牛会在其他牛之前到达聚会现场。现在你需要计算出所有牛到达聚会现场所需要的时间,并找出其中最长的那个时间,也就是说,如果所有牛同时出发,最后到达聚会现场的牛需要的时间是多少,而且这个时间要尽量短。
具体来说,题目给出了一个图,其中每个节点表示一头牛,每条边表示两头牛之间的道路,每条边都有一个长度,表示走过这条道路所需要的时间。同时,题目还给出了每头牛喝一杯牛奶所需要的时间。你需要计算出所有牛到达聚会现场所需要的时间,并找出其中最长的那个时间。
这道题可以使用 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算法计算任意两点之间的最短路径,只需要在之前的路径基础上加入新的边构成的新路径进行更新即可。
BZOJ2839:集合计数(容斥,组合数学)
这个问题是一个比较经典的容斥原理的应用题目。我们可以考虑使用容斥原理来求解这个问题。具体来说,我们可以考虑求出所有集合的个数,然后减去至少包含一个特定元素的集合的个数,再加上至少包含两个特定元素的集合的个数,以此类推,直到加上包含所有特定元素的集合的个数。
对于一个大小为n的集合,其子集的个数为2^n。因此,所有集合的个数为2^n。现在我们考虑如何计算至少包含一个特定元素的集合的个数。我们可以将这个特定元素看作是一个元素,然后考虑其余n-1个元素组成的集合的个数,即2^(n-1)。因此,至少包含一个特定元素的集合的个数为2^(n-1)。同理,至少包含两个特定元素的集合的个数为C(2,n)*2^(n-2),其中C(2,n)表示从n个元素中选取2个元素的组合数。
将以上结果代入容斥原理的公式中,即可得到最终的计数公式:
sum((-1)^k*C(k,n)*2^(n-k),k=0,1,...,n)
其中,sum表示对k从0到n进行求和,C(k,n)表示从n个元素中选取k个元素的组合数,2^(n-k)表示剩余元素组成集合的个数。