1 条题解

  • 3
    @ 2024-1-30 19:07:06

    考虑最终可能的答案,有以下几种形式:xaxaya+zbya + zby{0,1}y \in \{0, 1\}),wbwb

    前两种可以使用一遍 BFS 计算,关键在于第三种,不惜多用几个 bb 的代价来换取 aa 的减少。考虑接着用 BFS 计算,因为边权还是相等的。过程形如:

    • uu,出队
      • 枚举 uvu \to vO(m)\mathcal O(m)
        • 枚举 vwv \to wO(m)\mathcal O(m)
          • 如果 w∉{v}w \not\in \{v\}:更新 ww,入队

    这会在菊花上被卡满,O(m2)\mathcal O(m^2)。因此考虑优化。

    事实上一个 ww 只可能被更新一次,因此我们枚举 vwv \to w 时一旦成功松弛则可以删去 vwv \to w 的边(但是 uvu \to v 不能删去,因此我们 只在第二层 遍历一个可删的边表。链式前向星不难实现)。

    时间复杂度:考虑如果 w{v}w \in \{v\} 会发生什么:u,v,wu, v, w 构成了三元环。否则就是均摊 O(1)\mathcal O(1) 的(神奇吗?)。因为三元环的个数为 O(m1.5)\mathcal O(m^{1.5}) 个,因此总时间复杂度为 O(n+m1.5)\mathcal O(n + m^{1.5})


    常数被 xhz 卡爆了。

    • @ 2024-1-30 19:08:18

      irris 大神太强了。

  • 1

信息

ID
794
时间
5000ms
内存
1024MiB
难度
6
标签
递交数
69
已通过
4
上传者