ch12 - 最短路 II

炼金术士小图 II

• 分析：

  • 这里处理技巧与 ch10 章节中题目 【Watering Hole】中的类似，考虑设定一个超级源点，编号记为 n+1
  • n 种材料看作 n 个结点，再加一个编号为 n + 1 的结点表示起点（什么材料都没有），花费作为边权，问题转换为从起点到结点 n 的单源最短路问题
  • 建图
    • 从起点 n + 1 向代表材料的每个结点 i 连一条边权为 $p_i$ 的有向边，表示可以花费 $p_i$ 从“什么都没有”到“拥有材料 i”。
    • 对于 type = 1 类型的转化，从结点 $a_i$ 向 $b_i$ 连一条边权为 $c_i$ 的有向边。
    • 对于 type = 2 类型的分解，从结点 $a_i$ 向 $b_i$ 连一条边权为 $-c_i$ 的有向边。（花费 $-c_i$ 就表示赚取 $c_i$）
  • 跑 SPFA 求从起点 n + 1 到 n 的最短路。
    • 如果存在负环，说明可以赚取无限的利润。
    • 如果 d[n] < 0 ，说明得到材料 n 花费负数费用，即赚取了利润。
  • 注意整个图有 n + 1 个结点，负环的判断应该是存在边数 >= n+1 的最短路，而不是 >= n。（写 >= n 也不会出错，因为起点只有出边没有入边，不会在环中）

• 代码

  int main() {
      int m, pi;
      cin >> n >> m;
      // 每个点都和 n+1 节点相连
      for (int i = 1; i <= n; i++) {
          cin >> pi;
          G[n + 1].push_back({i, pi});
      }
      for (int i = 1; i <= m; i++) {
          int t, a, b, c;
          cin >> t >> a >> b >> c;
          if (t == 1)
              G[a].push_back({b, c});
          else
              G[a].push_back({b, -c});
      }
      // 从 n + 1 节点出发跑 spfa 算法
      // 计算到达 n 号节点的最短路长度
      bool flag = spfa(n + 1);
      if (flag || d[n] < 0) // 有负环 或 到 n 的最短路为负则存在利润
          cout << "lucky" << endl;
      else
          cout << d[n] << endl;
      return 0;
  }
  

  路况查询

• 分析：

  • 因为查询次数 q 较大，如果对于每次查询都去跑一次单源最短路，时间复杂度较高。

  • 本题是对于 Floyd 原理的应用。允许经过结点 k 时，Floyd 算法执行了以下代码

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
    }
    

    那么城市 x 解封时，表示允许经过结点 x ，将以上代码 k 改为 x 执行一遍即可。

  • 对于 type = 2 类型的询问

    • 先判断 x 和 y 的解封情况，可以通过 bool 数组标记和判断。
    • x 或 y 还未解封， 或 f[x][y] == 正无穷大，说明无法到达。
    • 否则输出 f[x][y] 。

• 代码：详见课本【例12.4】路况查询

Cow Hurdles

• 分析：

  • 最短路问题是希望路径边权之和最小，本题希望路径中的最大边权最小，只需要修改松弛操作即可。

  • 从数据范围看出如果每次询问跑一遍单源最短路，效率较低，用 Floyd 算法比较合适。

  • f[i][j] 原本表示 i 到 j 的路径中，最小的路径长度，改为表示 i 到 j 的路径中，最小的最大边权。

  • 将 Floyd 的状态转移从

    f[i][j] = min(f[i][j], f[i][k] + f[k][j])
    

    改为

    f[i][j] = min(f[i][j], max(f[i][k], f[k][j]))
    

    即可

    • f[i][k] + f[k][j] 表示经过 k 的路径中 i 到 j 的最短路长度，求路径总长度所以用加法。
    • max(f[i][k], f[k][j]) 是从经过 k 的路径中 i 到 j 的最大边权。

  • 最后如果 f[a][b] == 正无穷大，表示无法从 a 到达 b，输出 -1，否则输出 f[a][b] 。

• 代码：详见课本【例12.3】跳跃比赛