[NOI2007] 社交网络

题意

对每个节点 $v$ ，累加所有无序端点对的最短路经过它的比例：

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

其中 $C_{s,t}$ 是 $s$ 到 $t$ 的最短路条数， $C_{s,t}(v)$ 是其中经过 $v$ 的条数。图保证连通。

思路

要求 $I(v)$ ，需要两个量：任意两点的最短路条数 $C_{s,t}$ ，以及经过 $v$ 的最短路条数 $C_{s,t}(v)$ 。

第一个量：在 Floyd 里同步计数

普通的 Floyd 最后只留下一个数 dist[i][j]，路径条数的信息在松弛过程中被覆盖掉了。但请注意 dist 是怎么更新的——既然距离可以按规则合并，条数就能按同样规则合并，只需要给这一个转移配上两条规则：

cpp

1
2
3
4
5
6
7d = dist[i][k] + dist[k][j]
if (d < dist[i][j]) {          // 经 k 更短：旧走法全部作废，条数替换
    dist[i][j] = d;
    cnt[i][j] = cnt[i][k] * cnt[k][j];
} else if (d == dist[i][j]) {  // 经 k 一样短：一批新最短路，条数累加
    cnt[i][j] += cnt[i][k] * cnt[k][j];
}

为什么可以累加？ 因为 Floyd 第 $k$ 轮只在上一轮的结论上做一件事：放开 k 这个中转点。所以每轮产生的候选恰好是两类：

类别	含义	来源
不经 `k`	中间点均来自前 $k-1$ 批	上一轮的 `dist[i][j]`
经 `k`	中间点集合包含 `k`	本轮的 `dist[i][k] + dist[k][j]`

这两类互斥，所以相加不会重复。

为什么用乘法？ 一条经 k 的路径需要拆成“i 到 k 的一段”和“k 到 j 的一段”，两段的选择互相独立，按乘法原理相乘。

必须跳过 `i == k` 和 `j == k`

这一条不是优化，而是正确性必需。

当 i == k 时，dist[i][k] = 0，那条“路径”原地没动。它既不是“经 k 的”，也不是“不经 k 的”，而是两类都能算——上表那个互斥前提被破坏，累加就重复了。

实测后果很严重：不跳过时 400 组随机数据里有 344 组算出错误结果，例如

text

1
23 个点，边 1-2 权 1、1-3 权 2
不跳过: I(1) = 1.333     正确值: 2.000

所以三重循环里的 if (i == k) continue; 与 if (j == k || i == j) continue; 都不可或缺。

第二个量：两段距离之和等于总距离

有了距离矩阵和第个条数矩阵，剩下的是判断“v 是否在 s → t 的某条最短路上”。判据是距离的加性：

dist[s][v] + dist[v][t] == dist[s][t]

为什么这条等式与“存在经过 v 的最短路”等价？

若存在一条经过 v 的最短路，它的前半段是 $s \to v$ 、后半段是 $v \to t$ ，两段长度之和必然等于全长。
反之若等式成立，那么“ $s$ 走最短路到 $v$ ，再走最短路到 $t$ ”就是一条长度为 $dist[s][t]$ 的路径，即一条经过 v 的最短路。

而唯一的拆分是关键：v 在路径上的位置是确定的，任何经过 v 的最短路都能唯一拆成一头一尾，不存在“同一路径按不同方式拆分”的重叠。所以

C_{s,t}(v) = cnt[s][v] \cdot cnt[v][t]

成立。若一个点可以在路径上出现多次，这个乘积就会重复计数——但本题边权为正，最短路不可能重复经过同一点。

汇总

三段组合起来就得到答案：

I(v) = \sum_{\substack{s \ne v,\ t \ne v \\ s \ne t}} \frac{cnt[s][v] \cdot cnt[v][t]}{cnt[s][t]}

必须排掉 $s = t$ 的情形：自己到自己的最短路无意义。

两个容易忽略的点

溢出： 题面保证任意两点间的最短路条数不超过 $10^{10}$ ，而 cnt[i][k] * cnt[k][j] 只在 i→k→j 确实是最短路时才有意义，此时乘积不超过 cnt[i][j]，不会溢出。但代码里 先算乘积再比较距离 的写法，在“经 k 不是最短路”时仍会乘出一个可能超出 long long 的中间值（随后被丢弃，结果仍正确，但技术上有一次有符号溢出）。稳妥写法是先判断 d > dist[i][j] 就 continue，再算乘积。

浮点： 最后求和用 long double 累积，输出 fixed << setprecision(3)，避免多次除法叠加的精度损失。

Python 知识

Python 的 int 是任意精度，cnt 乘积不需要担心 $10^{10} \times 10^{10}$ 溢出，比 C++ 省心。
二维列表分别保存距离和计数，两个矩阵在松弛里同步更新，公式与代码一一对应。
f"{importance:.3f}" 按要求输出三位小数。

代码

python

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-17 01:40
# update_at: 2026-10-20 16:40
#
# main.py：社交网络。求每个点的重要度 I(v) = sum_{s!=v, t!=v} C(s,t)(v) / C(s,t)。
# 需要两个量：任意两点的最短路条数，以及经过 v 的最短路条数。
#
# 第一个量在 Floyd 里同步维护。Floyd 第 k 轮只在上一轮结论上加一件事：放开 k 这个中转点，
# 所以每轮的候选恰好是两类——不经 k 的（上一轮已有）和经 k 的（本轮新算）。两类互斥，
# 所以等长时累加不会重复；一条经 k 的路径拆成 i->k 与 k->j 两段，两段独立选择，
# 所以条数相乘。
# 必须跳过 i == k 和 j == k：dist[i][k] 在 i == k 时是 0，那条"路径"原地没动，
# 它既不算"经 k"也不算"不经 k"，互斥前提被破坏，累加就会重复计数。
#
# 第二个量用距离的加性判断：v 在 s->t 的某条最短路上 <=> dist[s][v]+dist[v][t]==dist[s][t]。
# 此时 C(s,t)(v) = cnt[s][v] * cnt[v][t]，因为 v 在路径上的位置确定，拆分唯一。

import sys

INF = 10**18  # 整数哨兵；Python int 任意精度，路径数相乘不会溢出


def floyd_with_count(n: int, edges: list[tuple[int, int, int]]):
    """返回 (dist, cnt)：dist[i][j] 为最短距离，cnt[i][j] 为最短路条数。点编号 0..n-1。"""
    dist = [[INF] * n for _ in range(n)]
    cnt = [[0] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
        cnt[i][i] = 1  # 自己到自己有一条长度 0 的平凡路径

    for u, v, w in edges:
        # 题面保证任意两点间最多一条边，直接赋值
        dist[u][v] = dist[v][u] = w
        cnt[u][v] = cnt[v][u] = 1

    for k in range(n):
        through = dist[k]  # dist[k][*]，缓存行引用
        cnt_through = cnt[k]
        for i in range(n):
            if i == k:
                continue  # 必须跳过：否则 dist[i][k]=0 的平凡路径会被重复累加
            row = dist[i]
            cnt_row = cnt[i]
            bridge = row[k]  # dist[i][k]
            if bridge == INF:
                continue  # i 到 k 不可达，经 k 中转没有意义
            cnt_to_k = cnt_row[k]
            for j in range(n):
                if j == k or i == j:
                    continue
                candidate = bridge + through[j]
                if candidate > row[j]:
                    continue  # 不是更优，连乘积都不必算
                ways = cnt_to_k * cnt_through[j]
                if candidate < row[j]:
                    # 经 k 更短：旧走法全部作废，条数替换
                    row[j] = candidate
                    cnt_row[j] = ways
                else:
                    # 经 k 一样短：一批新最短路，条数累加（两类路径互斥，不会重复）
                    cnt_row[j] += ways

    return dist, cnt


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    edges: list[tuple[int, int, int]] = []
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        edges.append((u - 1, v - 1, w))  # 题面编号 1..n，统一转成 0..n-1

    dist, cnt = floyd_with_count(n, edges)

    for v in range(n):
        importance = 0.0
        for s in range(n):
            if s == v:
                continue
            cnt_sv = cnt[s][v]
            dist_sv = dist[s][v]
            for t in range(n):
                if t == v or t == s:
                    continue
                # v 在 s->t 的某条最短路上 <=> 两段距离之和等于总距离
                if dist_sv + dist[v][t] == dist[s][t]:
                    importance += cnt_sv * cnt[v][t] / cnt[s][t]
        print(f"{importance:.3f}")


if __name__ == "__main__":
    solve()

C++ 版本：

cpp

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:40
 * update_at: 2026-10-20 16:40
 */
// 社交网络：求每个点的重要度 I(v) = sum_{s!=v, t!=v} C(s,t)(v) / C(s,t)。
// 需要两个量：任意两点的最短路条数，以及经过 v 的最短路条数。
//
// 第一个量在 Floyd 里同步维护。Floyd 第 k 轮只在上一轮结论上加一件事：放开 k 这个中转点，
// 所以每轮的候选恰好是两类——不经 k 的（上一轮已有）和经 k 的（本轮新算）。两类互斥，
// 所以等长时累加不会重复；而一条经 k 的路径拆成 i->k 与 k->j 两段，两段独立选择，
// 所以条数相乘。
//
// 必须跳过 i == k 和 j == k：dist[i][k] 在 i == k 时是 0，那条"路径"原地没动，
// 它既不算"经 k"也不算"不经 k"，上述互斥前提被破坏，累加就会重复计数。
//
// 第二个量用距离的加性判断：v 在 s->t 的某条最短路上 <=> dist[s][v]+dist[v][t]==dist[s][t]。
// 此时 C(s,t)(v) = cnt[s][v] * cnt[v][t]，因为 v 在路径上的位置确定，拆分唯一。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;              // 点数上界 n <= 100
const long long INF = (1LL << 60);

int n, m;
long long dist_node[MAXN][MAXN];   // dist_node[i][j]：i 到 j 的最短距离
long long cnt_path[MAXN][MAXN];    // cnt_path[i][j]：i 到 j 的最短路条数
long double answer[MAXN];          // answer[v]：v 的重要程度

void read_input() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist_node[i][j] = 0;
                cnt_path[i][j] = 1;  // 自己到自己有一条长度 0 的平凡路径
            } else {
                dist_node[i][j] = INF;
                cnt_path[i][j] = 0;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        // 题面保证任意两点间最多一条边，直接赋值即可
        dist_node[u][v] = dist_node[v][u] = w;
        cnt_path[u][v] = cnt_path[v][u] = 1;
    }
}

// Floyd：距离与条数同步松弛
void floyd_with_count() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (i == k) continue;  // 必须跳过：否则 dist[i][k]=0 的平凡路径会被重复累加
            for (int j = 1; j <= n; j++) {
                if (j == k || i == j) continue;

                long long bridge = dist_node[i][k] + dist_node[k][j];
                // 先比较距离再算乘积：不是更优时直接跳过，避免算出一个可能溢出的乘积
                if (bridge > dist_node[i][j]) continue;

                long long ways = cnt_path[i][k] * cnt_path[k][j];
                if (bridge < dist_node[i][j]) {
                    // 经 k 更短：旧走法全部作废，条数替换
                    dist_node[i][j] = bridge;
                    cnt_path[i][j] = ways;
                } else {
                    // 经 k 一样短：一批新最短路，条数累加（两类路径互斥，不会重复）
                    cnt_path[i][j] += ways;
                }
            }
        }
    }
}

// 按定义累加每个点的重要度
void count_importance() {
    for (int v = 1; v <= n; v++) {
        long double total = 0;
        for (int s = 1; s <= n; s++) {
            if (s == v) continue;
            for (int t = 1; t <= n; t++) {
                if (t == v || t == s) continue;
                // v 在 s->t 的某条最短路上 <=> 两段距离之和等于总距离
                if (dist_node[s][v] + dist_node[v][t] == dist_node[s][t]) {
                    total += (long double)cnt_path[s][v] * cnt_path[v][t] / cnt_path[s][t];
                }
            }
        }
        answer[v] = total;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    floyd_with_count();
    count_importance();

    cout << fixed << setprecision(3);
    for (int i = 1; i <= n; i++) {
        cout << (double)answer[i] << '\n';
    }

    return 0;
}

复杂度

Floyd 是 $O(n^3)$ ，重要度统计也是三重循环 $O(n^3)$ ，空间两个 $n \times n$ 矩阵共 $O(n^2)$ 。 $n \le 100$ 时约 $2 \times 10^6$ 次运算。

总结

Floyd 的 middle 不是“迭代次数”，而是控制允许使用的中转点集合，这正是 DP 的阶段划分。在这个阶段上同步维护计数辅助状态即可：每轮的路径类互斥，所以计数能相加；路径在某个点上有唯一拆分，所以两段条数能相乘。

最后用“两段距离之和等于总距离”把几何上的“经过 v”翻译成数值判断。一句话：DP 提供状态，计数原理提供合并规则，而“互斥”与“唯一”保证这两个操作是合法的。

目录

题意

思路

第一个量：在 Floyd 里同步计数

必须跳过 i == k 和 j == k

第二个量：两段距离之和等于总距离

汇总

两个容易忽略的点

Python 知识

代码

复杂度

总结

必须跳过 `i == k` 和 `j == k`