T3-7 Greg and Graph

思路分析

题目要求依次删点，每次删之前求所有点对最短路之和。

关键技巧：倒序处理，把"删点"变成"加点"。

删点的逆序就是加点。倒着看删除序列 $x_n, x_{n-1}, \ldots, x_1$，相当于依次加入点。每次加入一个新点 $k$ 时，用 Floyd 的思想：用 $k$ 作为中转点，更新所有已存在的点对之间的最短路。

$$d[i][j] = min(d[i][j], d[i][k] + d[k][j])$$

这恰好就是 Floyd 的第 $k$ 层循环——Floyd 本质上就是"逐个加入中转点"。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
const ll INF = 1e18;
ll d[N][N];          // d[i][j] = 当前已加入点集中，i 到 j 的最短路
ll w[N][N];          // 原始邻接矩阵
int x[N];            // 删除顺序
ll ans[N];           // ans[i] = 第 i 步删之前的答案
bool in[N];          // in[i] = 点 i 是否已加入
int main() {
    int n;
    cin >> n;
    // 读入邻接矩阵
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> w[i][j];
    // 读入删除顺序
    for (int i = 1; i <= n; i++)cin >> x[i];
    // 初始化 d 为 INF
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)d[i][j] = INF;
    // 倒序加入点，模拟 Floyd
    for (int step = n; step >= 1; step--) {
        int k = x[step];       // 本次加入的点
        in[k] = true;
        // 初始化：k 到已有点、已有点到 k 的直接边
        d[k][k] = 0;
        for (int i = 1; i <= n; i++) {
            if (!in[i]) continue;
            d[k][i] = w[k][i];
            d[i][k] = w[i][k];
        }
        // 用已有的中转点更新 k 相关的路径
        // 1. 更新 d[k][j]：k 到其他点，可能经过已有点中转
        for (int p = 1; p <= n; p++) {
            if (!in[p]) continue;
            for (int j = 1; j <= n; j++) {
                if (!in[j]) continue;
                d[k][j] = min(d[k][j], d[k][p] + d[p][j]);
            }
        }
        // 2. 更新 d[i][k]：其他点到 k，可能经过已有点中转
        for (int p = 1; p <= n; p++) {
            if (!in[p]) continue;
            for (int i = 1; i <= n; i++) {
                if (!in[i]) continue;
                d[i][k] = min(d[i][k], d[i][p] + d[p][k]);
            }
        }
        // 3. 用 k 作为中转，更新所有已有点对
        for (int i = 1; i <= n; i++) {
            if (!in[i]) continue;
            for (int j = 1; j <= n; j++) {
                if (!in[j]) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
        // 统计当前所有点对最短路之和
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            if (!in[i]) continue;
            for (int j = 1; j <= n; j++) {
                if (!in[j] || i == j) continue;
                sum += d[i][j];
            }
        }
        ans[step] = sum;
    }
    // 输出：ans[1] 是第 1 步删之前（所有点都在），ans[n] 是最后一步删之前（只剩一个点）
    for (int i = 1; i <= n; i++)cout << ans[i] << " \n"[i == n];
    return 0;
}

核心思想图示

删除顺序：4 → 1 → 2 → 3

倒序 = 加入顺序：3 → 2 → 1 → 4

step=4: 加入点 3        → ans[4] = 0（只有一个点）
step=3: 加入点 2        → ans[3] = d[2][3] + d[3][2]
step=2: 加入点 1        → ans[2] = 所有 {1,2,3} 间最短路之和
step=1: 加入点 4        → ans[1] = 所有 {1,2,3,4} 间最短路之和

每次加入点 k 时，用 Floyd 思想：
  先初始化 k 的直连边
  再用已有点更新 k 的路径
  最后用 k 更新所有已有点对

Floyd 算法 for k: for i: for j: d[i][j] = min(d[i][j], d[i][k]+d[k][j]) 的本质就是逐个加入中转点。把删点倒过来变成加点，每次加点就是 Floyd 的一层，天然匹配。