题目链接

E.飞翔的小鸟

出题人

$\color{orange}{sys.}$

题解

为了方便描述，我们规定 $k$ 为 $\max{h_i}$。

对于图无环的情况，我们可以使用动态规划解决。

$f[i][0]$ 表示从起点走到 $i$ 号点可以得到的最大边权。

$f[i][1]$ 表示从起点走到 $i$ 号点可以得到的最小边权。

$f[i][2]$ 表示从起点走到 $i$ 号点可以得到的最大答案。

则对于一条边 $(u,v,w)$ ，可进行如下转移：

$f[v][0]=\max(f[v][0],\max(f[u][0],w),f[v][1]=\min(f[v][1],\min(f[u][1],w))$ 。

$f[v][2]=\max(f[u][2],\max(f[v][0]-w,w-f[v][1]))$ 。

其中 $f[v][0]-w$ 表示将 $w$ 作为最小边权，$f[v][0]$ 作为最大边权。$w-f[v][1]$ 同理。

使用拓扑排序确定转移顺序。

对于一个环，我们发现如果将他全部走完，答案不会变得更劣。所以我们可以当遇到环时强制走一圈。

于是我们可以对图进行 $Tarjan$ 缩点。

对于图的重建，若一个强连通分量中存在大于等于 $2$ 个结点，我们就将这个强连通分量拆成三个点 $L,M,R$ ，$(L,M)$ 连一条权值为环中 $\max{h}$ 的边， $(M,R)$ 连一条 $\min{h}$ 的边。对于原图的边 $(u,v)$ ，我们建 $(R_{belong[u]},L_{belong[v]})$ ，其中 $belong[x]$ 表示 $x$ 所在的强连通分量。

之后我们便可以使用上述动态规划方法解决。

时间复杂度：$O(n+m)$ 。

AC 代码参考