题意

给定一个 $nm$ 的权值矩阵，求从左上角走到右下角。$(n, m \in [1, 100], w \in [1, 1e6])$

一条路径耗费的体力值是路径上相邻格子之间 高度差绝对值的最大值 决定的。

Solution

1. 二分答案：由于答案具有单调性，所以可以二分答案，然后通过 $bfs$ 进行验证。
2. 并查集：类似于最小生成树，将所有的边都建出来，然后贪心的将当前权值最小的边加入集合，判断起点和终点是否联通即可。
3. 最短路：将所有的边建出来，做一次起点到终点的最短路径即可。

题目

给定一个 $n$ 元有向完全图，每次操作可以翻转一条边。求最少的操作次数，使得图中不存在三元环。$(n <= 10)$

Solution