回到主页

信奥高级算法:一道求最短线路题

吉如一

· 算法教程

几个月前就已经打算写一个定期推荐好题目的文章,但是因为忙于准备 final,所以一直没有开始写。具体的形式大概和 Petr 博客最后的那样,推荐一道我自己觉得有意思的题目,大概以每周一至两道题的速度吧。

如果对于少儿编程感兴趣的话,可以到有渔编程和我进行交流。

在文章中我会给出题目的大致内容和分阶段的解题思路,但是大部分题目应该是没有公开的提交地址和数据的。如果想要实现并提交的话可以多找几个人大家对拍一下。

初期的题目以简单题为主,也希望大家给我一些反馈,我也会根据反馈在题目的难度上进行调整。同时如果碰到没有学习过的算法/数据结构的话也可以告诉我,我会在下一次的内容中加上一些比较好的博客/学习资料。

I、题目描述

给出一张 n 个点 m 条边的有向图 ,每经过第 i 条边一次会被收取 的路费,保证存在1 到 n 的路径。

正值五一,政府决定对所有从 1 到 n 的旅客,减免一定的路费。专家给出了常数 K,路费将按照如下的方式进行减免,对于一条从 1 到 n 的路径 p:

• 如果 p 中包含了小于等于 K 条边,则不作减免,即路费为所有经过的边的 的和。

• 如果p中包含了超过K条边,则只收取费用最高的K条边的路费,其余路费被减为0。下面是一个例子:

考虑路径 1 → 2 → 3 → 8:

• 当 K ≥ 3 的时候,因为这条路几种只有三条边,所以路费始终为 14。

• 当 K = 2 的时候,1 → 2 被减免了,路费为 12。

• 当 K = 1 的时候,1 → 2 和 2 → 3(或者 3 → 8)被减免了,路费为 6。

同时不难发现在这张图中无论 K 等于几,最优的路径都是 1 → 4 → 7 → 5 → 8。现在给出这张图以及常数 K,你需要计算从 1 到 n 最少需要多少路费。

数据范围 ,时间限制 3s。

 题解

前置技能

图上的单源最短路算法

单源最短算法

 暴力

在答案的路径中,一定存在一个临界值,使得大于等于临界值的所有边都需要缴纳路费, 小于临界值的所有边都不需要缴纳路费。

考虑枚举这个临界值 M ,则所有 小于 M 的道路在这种情况下都不需要支付路费,而

大于等于 M 的道路的路费仍然是 。

于是构造新图 ,把 G 中所有小于 M 的边都赋值为 0,其余边保持权值不变。一条路径的临界值可以是 M 当且仅当这条路径在 G 中经过了恰好 K 条没有被赋值为 0 的边。

于是我们需要求 1 到 n 经过了恰好 K 条非 0 边的所有路径中,边权和最小的路径。这可以在拆点后跑最短路,即新建一张 n × (K + 1) 个点的无向图 ,其中对于每一个原图中的点 ui,都新建 K + 1 个点 至 。对于原图中的一条 到 中的边,分情况考虑:

• 如果这条边边权为 0,则所有的 到 连一条边权为 0 的边。

• 如果这条边边权为 ,则所有的 到 连一条边权为 的边。

不难发现 的意义就是到达 i 经过了恰好 k 条非 0 边的最短路。那么 到 的最短路就是答案。

同时也要考虑经过的边不到 K 条的情况,这种情况只需要在 G 中跑一下 1 到 n 的最短路,和之前的答案取较小值(为什么?)。

在这个算法中,我们需要跑 次 个点, 条边的最短路,使用迪杰斯特拉算法可以达到 的时间复杂度。

上述算法其实是有问题的,考虑一条路径分别经过三条长度为 1, 2, 2 的边,在 K = 1 时:

• 如果枚举到临界值为 1,那么这时经过了两条非 0 边 2, 2,这条路径不会被计入答案

• 如果枚举到临界值大于等于 2,那么这时经过了零条非 0 边,这条路径也不会被计入答案。

解决方案很简单,我们可以人为的规定边的大小顺序:

把所有边按照边权从小到大排序, 边权相同的边任意排序。这时我们得到了边的一个顺序。之后我们就不必枚举确切的临界值了, 只需要枚举一条边 i,把排在他前面的边权都赋值为 0,在他之后的边权都保持不变。然后在这张图上用之前的方法求解恰好经过 K 条边的最短路即可(为什么这样就对了?)

通过这种方法,就能把时间复杂度降到 。

三分法求解单峰函数极值。

在这个问题中,令 f (i) 为我们选取的临界边为 i 的时候的最短路,那么最后的答案就是

,即求解函数 的极值。

如果函数 是凸的,那么可以三分求解,这样只需要求 次最短路即可,时间复杂度能降到 。

但是在这题中函数 不一定满足凸性,因此上述的方法就行不通了。(试着构造一下)

枚举一条临界边 i,按照如下方式变化每一条边的边权得到图

1、如果这条边排在 i 之后,那么把它的边权减去 。

2、 如果这条边排在 i 之前,那么把它的边权变成 0。

求出 中 1 到 n 的最短路,设长度为 d。将 作为候选解。

一共有 m + 1 张图 ,这样我们得到了 m + 1 个候选解,取最小值。同时和暴力做法一样,预先求一遍 G 的最短路来处理经过的边数不到 K 条的情况。这样得到的所有解中的最小值就是答案。

在这个做法中,只需要求 m 次 n 个点 m 条边的单源最短路,时间复杂度为 。如何证明这个做法的正确性?

只需要证明如下两点:

1. 对于每一条可能的路径,都存在一张图 使得在这张图中它的权值为实际值。

2. 对于每一条可能的路径,对于所有图 ,在这张图中它的权值大于实际值。

第一条很显然,对于一条经过边数小于等于 K 的路径,他在原图中权值等于实际值;对于一条经过边数大于 K 条的路径,设其第 K + 1 大的路径为 i,则它在 中权值等于实际值。

现在考虑第二条,仍然分情况讨论:

对于一条经过边数小于等于 K 的路径,他在 中,首先总边权被减去了至多 ,之后又被加上了 ,因此权值不会变小。

对于一条经过边数大于 K 的路径,他在原图中,所有边都被计入了总和中,因此权值不会变小。设这条路径中第 K + 1 大的路径为 j,在 中的权值分情况讨论:

• 如果 i 在 j 之后,那么这时路径中只有小于等于 K 条边在 中非 0,这些边在最后加上 后权值不变。但是这时,考虑所有在路径中是前 K 条但是在最短路中权值是 0 的边,他们的权值在最后都被记为 了,因此这些边的贡献不会减小,于是路径的总权值不会变小。

• 如果 i 在 j 之前,那么这时路径中有大于 K 条边在 中为 0,其中前 K 条边在加上 后权值不变,但是余下的边 k 实际的贡献为 0,但是在这时贡献为 ,因此这些边的贡献增加了,于是路径的总权值增加了。

综上所述,我们证明了这个贪心的算法是正确的。

所有文章
×

还剩一步!

确认邮件已发至你的邮箱。 请点击邮件中的确认链接,完成订阅。

好的