自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:43:37，当前版本为作者最后更新于2023-02-02 20:31:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8906 [USACO22DEC] Breakdown P

首先折半搜，将问题形式转化为维护 $1$ 到每个点经过 $k$ 条边的最短路 $h_i$，其中 $k\leq 4$。我们只考虑 $k = 4$。

删边倒过来变成加边。

考虑时刻维护任意两点间经过两条边的最短路 $f_{i, j}$。加边时只会对 $i = u$ 或 $j = v$ 的 $f_{i, j}$ 产生修改，共 $\mathcal{O}(n)$ 种情况。对于 $h_i$，枚举中转点 $j$ ，计算 $f_{1, j} + f_{j, i}$。注意到当且仅当 $i$ 或 $j$ 等于 $u$ 或 $v$ 时才会因 $f$ 的修改而对 $h$ 产生贡献，因此对于 $i\neq u, v$，只需用 $f_{1, u / v} + f_{u / v, i}$ 更新，对于 $i = u$ 或 $v$ 用所有 $f_{1, j} + f_{j, i}$ 更新。

单次加边的时间复杂度均摊 $\mathcal{O}(n)$，注意特判 $u = 1$。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 300 + 5;
constexpr int M = 1e5 + 5;
int n, m, k;
int ans[M], u[M], v[M], e[N][N];
void cmin(int &x, int y) {
  x = x < y ? x : y;
}
struct solver {
  int st, k;
  int e[N][N], f[N][N], h[N];
  void init(int _k, int _st) {
    k = _k, st = _st;
    memset(e, 0x3f, sizeof(e));
    memset(f, 0x3f, sizeof(f));
    memset(h, 0x3f, sizeof(h));
    if(!k) {
      h[st] = 0;
    }
  }
  void add(int u, int v, int w) {
    e[u][v] = w;
    if(!k) return;
    if(k == 1) {
      if(u == st) {
        h[v] = w;
      }
      return;
    }
    for(int i = 1; i <= n; i++) {
      cmin(f[i][v], e[i][u] + w);
      cmin(f[u][i], w + e[v][i]);
    }
    if(k == 2) {
      for(int i = 1; i <= n; i++) {
        cmin(h[i], f[st][i]);
      }
    }
    auto p = k == 3 ? e : f;
    if(k > 2) {
      if(u == st) {
        for(int i = 1; i <= n; i++) {
          for(int j = 1; j <= n; j++) {
            cmin(h[j], f[st][i] + p[i][j]);
          }
        }
      }
      else {
        for(int i = 1; i <= n; i++) {
          cmin(h[i], f[st][v] + p[v][i]);
          cmin(h[i], f[st][u] + p[u][i]);
          cmin(h[u], f[st][i] + p[i][u]);
          cmin(h[v], f[st][i] + p[i][v]);
        }
      }
    }
  }
} _1, _n;
int main() {
  #ifdef ALEX_WEI
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> k, m = n * n;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      cin >> e[i][j];
    }
  }
  for(int i = 1; i <= m; i++) {
    cin >> u[i] >> v[i];
  }
  int L = k >> 1, R = k - L;
  _1.init(L, 1), _n.init(R, n);
  for(int i = m; i; i--) {
    ans[i] = 0x3f3f3f3f;
    for(int p = 1; p <= n; p++) {
      cmin(ans[i], _1.h[p] + _n.h[p]);
    }
    _1.add(u[i], v[i], e[u[i]][v[i]]);
    _n.add(v[i], u[i], e[u[i]][v[i]]);
  }
  for(int i = 1; i <= m; i++) {
    if(ans[i] > 1e9) cout << "-1\n";
    else cout << ans[i] << "\n";
  }
  return 0;
}