1 条题解
-
3
考虑最终可能的答案,有以下几种形式:,(),。
前两种可以使用一遍 BFS 计算,关键在于第三种,不惜多用几个 的代价来换取 的减少。考虑接着用 BFS 计算,因为边权还是相等的。过程形如:
- ,出队
- 枚举 ()
- 枚举 ()
- 如果 :更新 ,入队
- 枚举 ()
- 枚举 ()
这会在菊花上被卡满,。因此考虑优化。
事实上一个 只可能被更新一次,因此我们枚举 时一旦成功松弛则可以删去 的边(但是 不能删去,因此我们 只在第二层 遍历一个可删的边表。链式前向星不难实现)。
时间复杂度:考虑如果 会发生什么: 构成了三元环。否则就是均摊 的(神奇吗?)。因为三元环的个数为 个,因此总时间复杂度为 。
常数被 xhz 卡爆了。
- ,出队
- 1
信息
- ID
- 794
- 时间
- 5000ms
- 内存
- 1024MiB
- 难度
- 6
- 标签
- 递交数
- 69
- 已通过
- 4
- 上传者