T1 [USACO22DEC] Breakdown P
比较显然的一点是，一次加一条边/一次删一条边，显然转化，这是显然的一条套路。
这题的 \(K\le8\)，很有意思的数据范围，然后调用我们聪明的人类大脑得知需要用到折半搜索。所以我们只考虑 \(K\le4\) 的情况，令 \(\mathit{st}\) 表示折半搜索中考虑的起点。维护 \(1\) 到 \(n\) 不超过 \(k\) 步的最短路 \(h_i\)，以及任意两点间经过两条边的最短路 \(f_{i,j}\)。假若我们要更新 \(u,v,w\)，然后就是神奇的部分：
- \(K=1\)，在 \(u=\mathit{st}\) 的情况下，更新 \(h_v=w\)；
- \(K=2\)，对 \(\forall1\le i\le n\)，更新 \(h_i\gets\min(h_i,f_{\mathit{st},i})\)；
- \(K=3\)，同理，用 \(f_{\mathit{st},i}+w\) 更新 \(h_i\)，其中 \(w\) 是两点间边权；
- \(K=4\)，同理，用 \(f_{st,i}+f\) 更新 \(h_i\)，其中 \(f\) 是你处理好的 \(f\)。
细节懒得说了，总之单次加边复杂度均摊 \(O(n)\)。然后就没了。
void cm(int &x, int y) {
x = x < y ? x : y;
}
constexpr int MAXN = 305;
int n, k, w[MAXN][MAXN], ans[MAXN * MAXN];
struct {
int u, v;
} del[MAXN * MAXN];
struct {
int st, k;
int w[MAXN][MAXN], f[MAXN][MAXN], h[MAXN];
void init(int _k, int _st) {
k = _k, st = _st;
memset(w, 0x3f, sizeof(w));
memset(f, 0x3f, sizeof(f));
memset(h, 0x3f, sizeof(h));
if (!k)h[st] = 0;
}
void add(int u, int v, int ww) {
w[u][v] = ww;
if (!k)return;
if (k == 1)return u == st && (h[v] = ww), void();
for (int i = 1; i <= n; ++i) {
cm(f[i][v], w[i][u] + ww);
cm(f[u][i], ww + w[v][i]);
}
if (k == 2)for (int i = 1; i <= n; ++i)cm(h[i], f[st][i]);
else {
auto p = k == 3 ? w : f;
if (u == st)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cm(h[j], f[st][i] + p[i][j]);
else
for (int i = 1; i <= n; ++i) {
cm(h[i], f[st][v] + p[v][i]);
cm(h[i], f[st][u] + p[u][i]);
cm(h[u], f[st][i] + p[i][u]);
cm(h[v], f[st][i] + p[i][v]);
}
}
}
} s, t;
signed main() {
// freopen("data.in","r",stdin);
n = read(), k = read();
for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)w[i][j] = read();
for (int i = 1; i <= n * n; ++i)del[i] = {read(), read()};
s.init(floor(k * 0.5), 1), t.init(ceil(k * 0.5), n);
for (int i = n * n; i; --i) {
ans[i] = 1e9;
for (int j = 1; j <= n; ++j)cm(ans[i], s.h[j] + t.h[j]);
s.add(del[i].u, del[i].v, w[del[i].u][del[i].v]);
t.add(del[i].v, del[i].u, w[del[i].u][del[i].v]);
}
for (int i = 1; i <= n * n; ++i)write(ans[i] == 1e9 ? -1 : ans[i]);
return fw, 0;
}