题目描述：
给出一张无向图，每条边都有一个最大承重值，现在要从起点走到终点，求出一条路径，使得路径上所有边的最小承重值最大。
输入格式：
第一行一个整数T，表示数据组数。
每组数据第一行是两个整数N和M，N表示点的个数，M表示边的个数。
接下来M行，每行三个整数a b c，表示点a和点b之间有一条边，承重为c。
最后一行是两个整数S和E，表示起点和终点。
输出格式：
每组数据输出一行，一个整数，表示最大的最小承重值。
解题思路：
这是一个经典的二分图问题，可以使用二分搜索结合深度优先搜索（DFS）或者广度优先搜索（BFS）来解决。
- 二分搜索范围：最小承重值的范围在所有边权重的最小值到最大值之间。我们可以对这个范围进行二分搜索。
- 可行性检查：在二分搜索的每一步，我们需要检查是否存在一条从起点到终点的路径，使得路径上所有边的最小承重值不小于当前二分搜索的中值。这可以通过DFS或BFS来实现。
- DFS/BFS实现：在DFS或BFS过程中，我们只考虑那些承重大于等于当前中值的边。
具体步骤如下：
- 读取输入：读取所有数据，构建图的邻接表。
-
二分搜索：
- 初始化二分搜索的上下界，下界为所有边权重的最小值，上界为最大值。
- 在每次二分搜索中，取中值，检查是否存在从起点到终点的有效路径。
- 如果存在，则说明当前中值可行，调整下界；否则调整上界。
- 输出结果：对于每组数据，输出最大的最小承重值。
代码实现（Python示例）：
def main():
import sys
input = sys.stdin.read
data = input().split()
index = 0
T = int(data[index])
index += 1
results = []
for _ in range(T):
N = int(data[index])
M = int(data[index + 1])
index += 2
from collections import defaultdict
graph = defaultdict(list)
edge_weights = []
for __ in range(M):
a = int(data[index])
b = int(data[index + 1])
c = int(data[index + 2])
index += 3
graph[a].append((b, c))
graph[b].append((a, c))
edge_weights.append(c)
S = int(data[index])
E = int(data[index + 1])
index += 2
def can_reach(mid):
from collections import deque
queue = deque([S])
visited = set([S])
while queue:
node = queue.popleft()
if node == E:
return True
for neighbor, weight in graph[node]:
if weight >= mid and neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return False
low, high = min(edge_weights), max(edge_weights)
best = 0
while low <= high:
mid = (low + high) // 2
if can_reach(mid):
best = mid
low = mid + 1
else:
high = mid - 1
results.append(best)
for result in results:
print(result)if name == "main": main()
说明：
- 输入读取：使用
sys.stdin.read一次性读取所有输入，然后通过索引分割处理。 - 图构建：使用邻接表存储图，每个节点存储其邻居和对应的边权重。
- 二分搜索：通过二分搜索确定最大的最小承重值。
- 可行性检查：使用BFS检查在当前中值下是否存在从起点到终点的路径。
这个代码实现了题目要求的功能，通过二分搜索和BFS结合的方式高效地解决了问题。可以根据实际需要调整和优化。
发表回复