讨论 比赛 【题解&答疑】Contest #14 E 题《飞翔的小鸟》

【题解&答疑】Contest #14 E 题《飞翔的小鸟》 比赛:Comet OJ - Contest #14

题目链接

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 代码参考

lok666 发起于2019-11-8 22:16:21 收起
分享
举报
删除
共0条回复
最新
成为第一个回复讨论的人吧~
全屏