Codeforces 295B 《Greg and Graph》

九月 30, 2018 3055

开倒车 倒序 Floyd

题目链接

题目描述

翻译来自洛谷

Greg有一个有边权的有向图，包含 n 个点。这个图的每两个点之间都有两个方向的边。Greg喜欢用他的图玩游戏，现在他发明了一种新游戏：

  • 游戏包含 n 步。
  • 第 i 步Greg从图中删掉编号为 x_i 的点。当删除一个点时，这个点的出边和入边都会被删除。
  • 在执行每一步之前，Greg想知道所有点对间最短路长度的和。最短路可以经过任何没删掉的点。换句话说，如果我们假设 d(i, v, u) 是在删掉 x_i 前 v 和 u 间的最短路长度，那么Greg想知道下面这个求和的值：MATHJAX-SSR-509

帮帮Greg，输出每一步之前要求的值。

Input / Output 格式 & 样例

输入格式

第一行包含一个整数 n \ (1 \leq n \leq 500) ，代表图中的点数。

下面 n 行每行包含 n 个整数，代表边权：第 i 行的第 j 个数 a_{ij} \ (1 \leq a_{ij} \leq 10^5, a_{ii} = 0) 代表从 i 到 j 的边权。

最后一行包含 n 个整数： x_1, x_2, \dots, x_n \ (1 \leq x_i \leq n) ，分别为Greg每一步删掉的点的编号。

输出格式

输出 n 个整数，第 i 个数等于游戏的第 i 步之前统计的求和值。

请不要在C++中使用%lld标志来输出64位整数long long，推荐使用cin, cout流或者用%I64d标志。

输入样例

Case #1: 

1
2
3
1
0
1

Case #2:

1
2
3
4
2
0 5
4 0
1 2

Case #3:

1
2
3
4
5
6
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3

输出格式

Case #1:

1
0

Case #2:

1
9 0

Case #3:

1
17 23 404 0

解析

n \le 500

很明显跑 Floyd 了

但是 Floyd 不支持删除操作

怎么办？

开倒车 倒序添加！

我们记录下删除点的信息，再倒着添加回去，在这个过程中套一个 Floyd 进去

要注意的是累计答案的时候判断点是否存在

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAXN = 500 + 10;

int f[MAXN][MAXN];
int seq[MAXN];
long long int ans[MAXN];

bool inGraph[MAXN];

int n;

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool returnValue) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (returnValue) putchar('\n');
}

inline void addEdge(int s, int t, int w) {
    f[s][t] = f[t][s] = w;
}

int main(int argc, char *const argv[]) {
    n = getint();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            f[i][j] = getint();
        }
    }
    for (int i = 1; i <= n; ++i) {
        seq[i] = getint();
    }
    for (int l = n; l > 0; --l) {
        int k = seq[l];
        inGraph[k] = true;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = std::min(f[i][j], f[i][k] + f[k][j]);
                if (inGraph[i] && inGraph[j]) ans[l] += f[i][j];
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
    return 0;
}