社区 › 科技 › P1948 USACO08JAN Telephone Lines S / AcWing 340. 通信线路 - 题解

敖雨燕 发表于 2025-8-25 16:13:55

P1948 USACO08JAN Telephone Lines S / AcWing 340. 通信线路 - 题解

https://www.luogu.com.cn/problem/P1948
https://www.acwing.com/problem/content/description/342/
方法一 分层图

每次选择从当前点前往另一点时要不要选择付费, 最多选择 \(k\) 次不付费, 所以就是 \(k + 1\) 层图.
具体来说, 假设 \(lev(u, i)\) 为第 \(i\) 层图的 \(u\) 点, 如果对于 \(u\) 如果有一条到 \(v\) 的边, 权值为 \(w\), 那就先在每层 \(lev(u, i) \leftrightarrow lev(v, i)\) 建权值为 \(w\) 的双向边, 再在 \(lev(u, i) \rightarrow lev(v, i + 1)\) 和 \(lev(v, i) \rightarrow lev(u, i +1)\) 建权值为 \(0\) 的单向边, 表示做出了一次不付费的选择, 单向边防止再回来, 确保最多只能做 \(k\) 次不付费选择.
接着跑 \(dijkstra\), \(dist_i\) 表示从 \(1\) 到 \(s\) 的所有路径中权值最大的边权值最小, 然后找出 \(dist_{lev(n, 0, 1, 2 \cdots k)}\) 中最小的那个即可.
#include #include #include #include #include #include using namespace std;#define DLN(x) cout

抽厉 发表于 2025-10-27 19:31:36

东西不错很实用谢谢分享

菅舛 发表于 2025-11-2 12:20:32

前排留名，哈哈哈

骆贵 发表于 2025-12-12 12:25:59

新版吗？好像是停更了吧。

支智敏 发表于 2026-1-2 19:35:19

感谢分享

旁拮猾 发表于 2026-1-3 22:07:25

新版吗？好像是停更了吧。

腥狩频 发表于 2026-1-15 20:55:27

喜欢鼓捣这些软件，现在用得少，谢谢分享！

碛物 发表于 2026-1-18 06:46:15

yyds。多谢分享

梁宁 发表于 2026-1-20 16:50:05

这个有用。

坏级尹 发表于 2026-1-21 06:46:28

过来提前占个楼

忙贬 发表于 2026-1-21 09:58:36

谢谢分享，试用一下

颜清华 发表于 2026-1-24 07:43:08

谢谢楼主提供！

全愉婉 发表于 2026-1-30 08:08:10

这个好，看起来很实用

喳谍 发表于 2026-2-3 06:47:43

懂技术并乐意极积无私分享的人越来越少。珍惜

矛赓宁 发表于 2026-2-4 08:26:23

东西不错很实用谢谢分享

顶豌 发表于 2026-2-8 08:39:19

收藏一下   不知道什么时候能用到

坪钗 发表于 2026-2-8 12:27:44

这个有用。

董绣梓 发表于 2026-2-9 01:11:32

鼓励转贴优秀软件安全工具和文档！

喳谍 发表于 2026-2-9 02:16:48

懂技术并乐意极积无私分享的人越来越少。珍惜

孟茹云 发表于 2026-2-9 17:35:44

很好很强大我过来先占个楼 待编辑

查看完整版本: P1948 USACO08JAN Telephone Lines S / AcWing 340. 通信线路 - 题解