题目描述

在社交网络（social network）的研究中，我们常常使用图论概念去解释一些社会现象。

在一个社交圈子里有 $n$ 个人，人与人之间有不同程度的关系。

我们将这个关系网络对应到一个 $n$ 个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值 $c$，$c$ 越小，表示两个人之间的关系越密切。

我们可以用对应结点之间的最短路长度来衡量两个人 $s$ 和 $t$ 之间的关系密切程度，注意到最短路径上的其他结点为 $s$ 和 $t$ 的联系提供了某种便利，即这些结点对于 $s$ 和 $t$ 之间的联系有一定的重要程度。

我们可以通过统计经过一个结点 $v$ 的最短路径的数目来衡量该结点在社交网络中的重要程度。

考虑到两个结点 $A$ 和 $B$ 之间可能会有多条最短路径。

我们修改重要程度的定义如下：令 $C_{s,t}$ 表示从 $s$ 到 $t$ 的不同的最短路的数目，$C_{s,t}(v)$ 表示经过 $v$ 的从 $s$ 到 $t$ 的最短路的数目；

则定义

$$I(v) = \sum_{s \neq v, t \neq v} \frac{C_{s,t}(v)}{C_{s,t}}$$

为结点 $v$ 在社交网络中的重要程度。

现在给出这样一幅描述社交网络的加权无向图，请你求出每一个结点的重要程度。

输入格式

输入第一行有两个整数 $n$ 和 $m$，表示社交网络中结点和无向边的数目。

在无向图中，我们将所有结点从 $1$ 到 $n$ 进行编号。

接下来 $m$ 行，每行用三个整数 $a, b, c$ 描述一条连接结点 $a$ 和 $b$，权值为 $c$ 的无向边。

注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过 $10^{10}$。

输出格式

输出包括 $n$ 行，每行一个实数，精确到小数点后 $3$ 位。

第 $i$ 行的实数表示结点 $i$ 在社交网络中的重要程度。

样例

4 4
1 2 1
2 3 1
3 4 1
4 1 1

1.000
1.000
1.000
1.000

样例解释

输入

$n=4, m=4$ 边： 1-2 (1), 2-3 (1), 3-4 (1), 4-1 (1)

这是一个四边形，所有边权为 1。

计算

对于任意两个结点 $s$ 和 $t$，最短路径长度等于它们之间的边数（因为边权相等）。

考虑结点 1：

• $s=2, t=3$：最短路径有两条：2→1→3 和 2→3。经过 1 的路径只有 2→1→3，所以贡献 $1/2$。
• $s=2, t=4$：最短路径有两条：2→1→4 和 2→3→4。经过 1 的路径只有 2→1→4，贡献 $1/2$。
• $s=3, t=4$：最短路径有两条：3→4 和 3→2→1→4？不对，3→4 直接距离 1，3→2→1→4 距离 3，不是最短路径。所以最短路径只有一条：3→4，不经过 1，贡献 0。
• $s=3, t=2$：类似 $s=2,t=3$，贡献 $1/2$。
• $s=4, t=2$：类似 $s=2,t=4$，贡献 $1/2$。
• $s=4, t=3$：最短路径一条：4→3，不经过 1，贡献 0。

所以 $I(1) = 1/2 + 1/2 + 1/2 + 1/2 = 2$？但输出是 1.000。

等等，公式是 $I(v) = \sum_{s \neq v, t \neq v} \frac{C_{s,t}(v)}{C_{s,t}}$，其中 $s$ 和 $t$ 都不等于 $v$，且 $s < t$？还是 $s \neq t$ 且均不等于 $v$？通常我们理解为无序对 $(s,t)$，$s < t$ 且 $s,t \neq v$。否则每个无序对会被计算两次（$s,t$ 和 $t,s$），但公式中求和符号没有限制，所以是 $s \neq v, t \neq v$，且 $s$ 和 $t$ 可以相同吗？如果 $s=t$，那么 $C_{s,t}=1$，$C_{s,t}(v)$ 要么 0 要么 1（如果 $s=v$ 则不算），但 $s \neq v$ 且 $t \neq v$，所以 $s=t$ 时 $C_{s,t}=1$，$C_{s,t}(v)=0$（因为路径就是点本身，不经过其他点）。所以贡献为 0。因此可以忽略 $s=t$。

如果按照无序对计算，则上述例子中 $s,t$ 对： (2,3), (2,4), (3,4) 对于 $v=1$：

• (2,3)：贡献 1/2
• (2,4)：贡献 1/2
• (3,4)：贡献 0 总和 1.000。

所以输出 1.000。

同理，其他结点对称，都是 1.000。

数据范围

• $n \le 100$
• $m \le 4500$
• $1 \le c \le 1000$
• 任意两点间最短路数目不超过 $10^{10}$

算法分析

这是一个全源最短路计数问题，并且要求计算每个点作为中间点出现在最短路径中的比例。

步骤

1. 使用 Floyd-Warshall 算法求出所有点对之间的最短距离 $dist[i][j]$，同时计算点对之间的最短路数目 $cnt[i][j]$。
2. 对于每个点 $v$，计算 $I(v)$。

Floyd-Warshall 同时计数

初始化：

• $dist[i][j] = w(i,j)$ 如果 $i$ 和 $j$ 有边，否则 $+\infty$，$dist[i][i]=0$。
• $cnt[i][j] = 1$ 如果 $i$ 和 $j$ 有边，否则 $0$，$cnt[i][i]=1$（自己到自己的路径数为1）。

在 Floyd 过程中，当发现更短的路径时，更新 $dist$ 和 $cnt$；当发现相等长度的路径时，累加 $cnt$。

具体：

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
        cnt[i][j] = cnt[i][k] * cnt[k][j]
      else if dist[i][k] + dist[k][j] == dist[i][j]:
        cnt[i][j] += cnt[i][k] * cnt[k][j]

注意：$cnt[i][j]$ 可能很大，但题目保证不超过 $10^{10}$，可以用 long long 存储。

计算 $I(v)$

对于每个点 $v$，枚举所有点对 $(s,t)$，$s \neq v, t \neq v, s < t$（避免重复），计算 $C_{s,t}(v)$。

如何计算 $C_{s,t}(v)$？即经过 $v$ 的 $s$ 到 $t$ 的最短路径数目。

如果 $v$ 在 $s$ 到 $t$ 的最短路径上，那么 $dist[s][t] = dist[s][v] + dist[v][t]$。

此时，$C_{s,t}(v) = cnt[s][v] \times cnt[v][t]$。

但需要注意：如果 $s$ 到 $v$ 的最短路径和 $v$ 到 $t$ 的最短路径有重叠，这样计算可能会重复计数？实际上，由于是最短路径，$s$ 到 $v$ 的最短路径和 $v$ 到 $t$ 的最短路径在 $v$ 处连接，只要 $v$ 不在 $s$ 到 $v$ 的路径中（除了端点）且不在 $v$ 到 $t$ 的路径中（除了端点），那么 $cnt[s][v] \times cnt[v][t]$ 就是经过 $v$ 的路径数。但 $v$ 是中间点，所以 $s$ 到 $v$ 的路径中 $v$ 是终点，$v$ 到 $t$ 的路径中 $v$ 是起点，所以不会重叠。

因此，如果 $dist[s][t] == dist[s][v] + dist[v][t]$，则 $C_{s,t}(v) = cnt[s][v] \times cnt[v][t]$。

那么 $I(v) = \sum_{s \neq v, t \neq v, s < t} \frac{cnt[s][v] \times cnt[v][t]}{cnt[s][t]}$。

注意：$s$ 和 $t$ 是无序对，所以 $s < t$。

复杂度

• Floyd-Warshall $O(n^3)$，$n \le 100$，$100^3 = 1e6$，可接受。
• 计算 $I(v)$：$O(n^3)$（枚举 $v, s, t$），也可接受。

实现细节

• 使用 double 存储 $I(v)$，虽然 $cnt$ 是整数，但除法结果可能是小数。
• 注意 $cnt$ 可能为 0（如果 $s$ 和 $t$ 不连通），但题目保证图连通，所以 $cnt[s][t] > 0$。
• 初始化 $cnt[i][j]$：如果 $i$ 和 $j$ 有边，则 $cnt[i][j]=1$，否则为 0（除了 $i=j$ 时为 1）。
• Floyd 中，$cnt[i][j]$ 更新时，如果发现更短路径，则直接赋值 $cnt[i][k] * cnt[k][j]$；如果发现相等路径，则累加。注意乘法可能溢出，但题目保证不超过 $10^{10}$，long long 足够。

样例验证

对于样例，通过 Floyd 得到： 所有点对之间最短距离均为 1（相邻）或 2（对角）。 $cnt$ 矩阵：

• 相邻点：$cnt=1$
• 对角点：$cnt=2$（因为有两种最短路径）

计算 $I(1)$：

• $s=2, t=3$：$dist[2][3]=1$，$dist[2][1]+dist[1][3]=1+1=2$，不相等，所以 $v=1$ 不在 $2\to3$ 的最短路径上，贡献 0。
• $s=2, t=4$：$dist[2][4]=2$，$dist[2][1]+dist[1][4]=1+1=2$，相等。$cnt[2][1]=1$，$cnt[1][4]=1$，$cnt[2][4]=2$，贡献 $1\times1/2=0.5$。
• $s=3, t=4$：$dist[3][4]=1$，$dist[3][1]+dist[1][4]=1+1=2$，不相等，贡献 0。 所以 $I(1)=0.5$？但输出是 1.000。

我们需要检查：$s=2,t=3$ 的最短路径是否经过 1？$2\to3$ 直接距离 1，路径不经过 1。所以贡献 0 正确。 $s=3,t=2$ 与 $s=2,t=3$ 是同一个无序对，只算一次。 $s=4,t=2$ 与 $s=2,t=4$ 是同一个无序对。 $s=4,t=3$ 与 $s=3,t=4$ 是同一个无序对。 所以只有 (2,4) 这一对贡献 0.5，总和 0.5，不是 1。

但输出是 1，说明我们漏了其他对。

考虑 $s=2, t=3$ 是否经过 1？不经过。 也许 $s=2, t=3$ 的最短路径有两条：2→1→3 和 2→3，所以 $cnt[2][3]=2$，$dist[2][3]=1$？不对，2→1→3 距离为 2，不是最短路径。所以只有一条 2→3。

所以我们的计算似乎不对。

实际上，图是一个四边形，边权均为 1。 点对最短距离：

• 相邻点：距离 1，路径数 1
• 对角点：距离 2，路径数 2（两条边组成的路径）

对于 $v=1$，考虑无序对 $(s,t)$：

1. (2,3)：最短距离 1，不经过 1。
2. (2,4)：最短距离 2，经过 1 的路径是 2→1→4，另一条是 2→3→4。所以 $C_{2,4}(1)=1$，$C_{2,4}=2$，贡献 0.5。
3. (3,4)：最短距离 1，不经过 1。

总和 0.5。

但答案应为 1，说明还有 (3,2) 和 (4,2) 等？但这些都是重复的。

可能公式中 $s$ 和 $t$ 是有序的，即 $s \neq v, t \neq v$，且 $s$ 可以等于 $t$？但 $s=t$ 时 $C_{s,t}(v)=0$，不影响。

如果 $s$ 和 $t$ 有序，那么 $s=2,t=4$ 和 $s=4,t=2$ 都要算，贡献 0.5+0.5=1。再加上 $s=3,t=4$ 和 $s=4,t=3$ 都不经过 1，所以 $I(1)=1$。

同理 $s=2,t=3$ 和 $s=3,t=2$ 都不经过 1。

所以总和为 1。

因此，公式中的求和是有序对 $(s,t)$，其中 $s \neq v, t \neq v$。

修正算法

$I(v) = \sum_{s \neq v} \sum_{t \neq v} \frac{C_{s,t}(v)}{C_{s,t}}$，其中 $s$ 和 $t$ 独立遍历 $1..n$，且都不等于 $v$。

计算时，对于每个 $v$，枚举 $s$ 和 $t$，如果 $dist[s][t] == dist[s][v] + dist[v][t]$，则贡献 $cnt[s][v] * cnt[v][t] / cnt[s][t]$。

复杂度 $O(n^3)$。

实现

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
const long long INF = 1e18;

long long dist[N][N], cnt[N][N];
double ans[N];

int main() {
    int n, m;
    cin >> n >> m;

    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = (i == j) ? 0 : INF;
            cnt[i][j] = (i == j) ? 1 : 0;
        }
    }

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[b][a] = c;
        cnt[a][b] = cnt[b][a] = 1;
    }

    // Floyd-Warshall
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    cnt[i][j] = cnt[i][k] * cnt[k][j];
                } else if (dist[i][k] + dist[k][j] == dist[i][j]) {
                    cnt[i][j] += cnt[i][k] * cnt[k][j];
                }
            }
        }
    }

    // 计算 I(v)
    for (int v = 1; v <= n; v++) {
        double res = 0.0;
        for (int s = 1; s <= n; s++) {
            if (s == v) continue;
            for (int t = 1; t <= n; t++) {
                if (t == v) continue;
                if (dist[s][t] == dist[s][v] + dist[v][t]) {
                    res += (double)(cnt[s][v] * cnt[v][t]) / cnt[s][t];
                }
            }
        }
        ans[v] = res;
    }

    for (int i = 1; i <= n; i++) {
        printf("%.3lf\n", ans[i]);
    }

    return 0;
}

总结

本题需要理解有序对求和，并使用 Floyd-Warshall 同时计算最短路数量和距离。注意数据范围，使用 long long 存储计数。