[Usaco2007 Feb]Cow Party

题目描述

一共有 $N$ 头奶牛，从 $1$ 到 $N$ 编号，它们的舞会在 $M$ 个房间中进行。每个房间只能容纳一头奶牛，每个房间的编号也为 $1$ 到 $N$。

有些房间之间有走廊相连，走廊有长度。奶牛只能从一个房间走到另一个房间，不能从走廊上行走。如果两个房间相连，则奶牛可以直接从一个房间走到另一个房间，而不需要通过其他房间。如果两个房间不相连，则奶牛需要在走廊上行走。

每头奶牛有能力值 $p_i$，且在舞会中只能负责一个房间。所以，如果有 $K$ 头奶牛在一个房间中，那么这个房间的能力值就是这 $K$ 头奶牛的能力值之和。如果有两个或更多的房间是相互连接的，那么它们可以组成一个房间，它们的能力值之和就是所有这些房间的能力值之和。

现在你需要知道，当所有奶牛聚在一起时，他们能否在 $T$ 秒内到达同一个房间。当一头奶牛到达一个房间时，它就可以停留在那里，等待其他奶牛到来。

输入格式

第一行包含三个整数 $N,M,T$。

第二行包含 $N$ 个整数，其中第 $i$ 个整数 $p_i$ 表示第 $i$ 头奶牛的能力值。

接下来 $M$ 行，每行包含三个整数 $a,b,c$，表示房间 $a$ 和房间 $b$ 之间存在一条长度为 $c$ 的走廊。

输出格式

如果所有奶牛可以在 $T$ 秒内到达同一个房间，则输出 Yes。

否则输出 No。

数据范围

$1≤N≤400,0≤M≤20000,1≤T≤10^9,1≤p_i,c≤100$

输入样例1：

3 3 10
1 2 3
1 2 1
2 3 2
1 3 3

输出样例1：

Yes

输入样例2：

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

输出样例2：

No

算法1

(最短路+二分答案) $O(N^3logN)$

首先，对于这道题目，我们可以将所有的房间缩成联通块，然后最后判断联通块中能力值最大的房间能不能在 $T$ 秒内到达其他房间。具体的，对于每个联通块，我们可以按照以下方式进行操作：

- 对于每个房间，其能力值为 $p_i$。
- 对于每个联通块中的边 $a, b, c$，我们可以将其表示为一个从 $a$ 到 $b$，长度为 $c$ 的边。
- 对于每个联通块，我们需要求出这个联通块的直径，即联通块中任意两个点之间的最短路径中，最长的一条路径长度。因为我们可以将所有的房间缩成一个点，所以直径的长度可以用两遍最短路来求得。

最后，我们需要判断联通块中能力值最大的点是否能够在 $T$ 秒内到达其他的房间。因为我们已经知道了联通块的直径长度，所以可以对直径长度进行二分，假设当前二分到的直径长度为 $mid$，则我们可以得到一个最小的时间 $t_{mid}$，使得联通块中任意两点之间的最短路径长度不超过 $mid$。如果 $t_{mid}≤T$，说明能力值最大的点可以在 $T$ 秒内到达其他房间，否则不能。

时间复杂度

对于每个联通块，需要求出直径，时间复杂度为 $O(N^3)$；对于每个联通块，我们需要进行二分答案，时间复杂度为 $O(logN)$。因此，总时间复杂度为 $O(N^3logN)$。

C++ 代码

算法2

(最短路+堆优化Dijkstra) $O(MlogM)$

首先将所有的房间缩成联通块，然后对于每个联通块，我们可以按照以下方式进行操作：

- 对于每个房间，其能力值为 $p_i$。
- 对于每个联通块中的边 $a, b, c$，我们可以将其表示为一个从 $a$ 到 $b$，长度为 $c$ 的边。
- 对于每个联通块，我们需要求出这个联通块的直径长度，即联通块中任意两个点之间的最短路径中，最长的一条路径长度。因为我们可以将所有的房间缩成一个点，所以直径的长度可以用两遍最短路来求得。

最后，我们需要判断联通块中能力值最大的点是否能够在 $T$ 秒内到达其他的房间。因为我们已经知道了联通块的直径长度，所以可以对直径长度进行二分，假设当前二分到的直径长度为 $mid$，则我们可以通过堆优化的 Dijkstra 算法，求得一个最小的时间 $t_{mid}$，使得联通块中任意两点之间的最短路径长度不超过 $mid$。如果 $t_{mid}≤T$，说明能力值最大的点可以在 $T$ 秒内到达其他房间，否则不能。

时间复杂度

对于每个联通块，需要求出直径，时间复杂度为 $O(MlogM)$；对于每个联通块，我们需要进行二分答案，时间复杂度为 $O(logN)$。因此，总时间复杂度为 $O(MlogM+N^2logN)$。

C++ 代码