「Floyd」社交网络

本题为3月13日23上半学期集训每日一题中B题的题解

可前往我的博客中阅读

题面

题目描述

在社交网络（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 eq v,t eq v} frac{C_{s,t}(v)}{C_{s,t}}) 为结点v在社交网络中的重要程度。

为了使 (I(v)) 和 (C_{s,t}(v)) 有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。

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

输入

第一行有两个整数，n和m，表示社交网络中结点和无向边的数目。在无向图中，我们将所有结点从1到n进行编号。

接下来m行，每行用三个整数a, b, c描述一条连接结点a和b，权值为c的无向边。注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

输出

包括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

提示

社交网络如下图所示。

对于1号结点而言，只有2号到4号结点和4号到2号结点的最短路经过1号结点，而2号结点和4号结点之间的最短路又有2条。因而根据定义，1号结点的重要程度计算为1/2+1/2=1。由于图的对称性，其他三个结点的重要程度也都是1。

50%的数据中： (nleq 10，mleq 45)

100%的数据中： (nleq 100，mleq 4500) ，

任意一条边的权值c是正整数，满足： (1leq cleq 1000) 所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过1010。

思路分析

想要求出最短路的条数,显然首先要求出最短路的长度(或者说是需要去求最短路的长度).此题为多源最短路问题,且节点数较小,所以可以尝试采用Floyd算法来解决.

如果你不知道什么是Floyd算法,请自行搜索学习,这里贴两篇个人找到的博客,这篇博客可以用来学习一下Floyd算法的基本知识,这篇博客可以用来学习更多的内容,如正确性证明等.也可自行搜索别的博客、视频、书籍等进行学习,这里不过多赘述.

由题意,我们需要维护出每两个点之间最短路的条数,以及这些最短路中经过某个点的条数.简单回忆Floyd算法求解最短路的过程可知:

• 当一个中间点可以减少两个点之间的距离时,我们便用这个中间点来松弛这条边,此时,我们可以认为这个中间点加入了那两个点暂时的(或者说当前递推阶段的)最短路中(不理解这句话建议回去看看Floyd算法),我们可以由此,加上分步乘法计数原理,便计算出每个递推阶段中两个点之间最短路的数量;
• 当我们用一个中间点尝试松弛一条边时,如果发现它松弛后的结果与这两个点当前阶段递推出来的最短距离是一致的,那么就说明这个点作为中间点也可以在当前阶段产生出同样长度的最短路.根据分类加法计数原理,我们可以以此来更新(或者说补充)当前阶段中两个点之间最短路的数量.

但是Floyd算法是一个动态的算法,如何在这个动态的过程中维护出最终的最短路数量呢?我们可以和Floyd算法一样,再开一个维度表示阶段(即当前正在用来松弛的点的编号),使用动态规划的方法进行维护.可得如下状态转移方程( (dp[k][i][j]) 表示当前用点k来松弛时,点i到j之间最短路的数量):

(dp[k][i][j] = egin{cases} 0, k = 0且(i,j)之间没有直接的边相连\ 1, k = 0且(i,j)之间有直接的边相连(由于还未开始松弛,所以认为这条边就是最短路)\ dp[k - 1][i][k] imes dp[k - 1][k][j], k eq 0且当前k能松弛点对(i,j)之间的距离\ dp[k - 1][i][j] + dp[k - 1][i][k] imes dp[k - 1][k][j], k eq 0且当前k松弛后与原本点对(i,j)之间的最短距离一致\ dp[k - 1][i][j], k eq 0且当前k不能松弛点对(i,j)之间的距离 end{cases})

显然,这个状态转移方程也可以使用和Floyd算法同样的方法来进行空间压缩,去掉这个表示阶段的维度,最终我们可以得到一个和Floyd几乎完全一致的形式.由于能进行空间压缩的原因以及方式和Floyd算法几乎完全一致,所以此处不多赘述,直接展示空间压缩后的状态转移规则:

• 初始时,还未开始松弛,此时我们认为两个点之间的最短距离就是它们之间连着的边的距离,此时直接相连的点对 ((i,j)) 之间有一条当前阶段的最短路, (dp[i][j] = 1) ,而之间没有边直接相连的点对 ((i,j)) 之间没有当前阶段的最短路, (dp[i][j] = 0) .
• 在Floyd递推的过程中,如果当前中间点k能够用来松弛点对 ((i,j)) 之间的距离,那么在松弛的同时,我们将 $ dp[i][j] $ 重新计算为 $ dp[i][k] imes d[k][j] $ ,即当前阶段i到k的最短路数量和k到j的最短路数量之积(因为这里是两段路,视为两步,所以使用分步乘法计算原理).
• 在Floyd递推的过程中,如果当前中间点k尝试松弛点对 ((i,j)) 之间的距离时,发现他和当前点对之间的最短距离一致,证明通过这个点也能产生最短路,我们将 $ dp[i][j] $ 加上 $ dp[i][k] imes d[k][j] $ ,把这一段最短路的数量算上.

如此,我们只需要在Floyd的过程中,同步进行对dp数组的操作,即可维护出最终每一对点之间最短路径的数量.

然后我们再来看题目要求的这个式子,这是一个累加式,我们需要求出,每一个点对(s,t)之间的最短路数量,以及这些最短路中经过点v的最短路数量.其中,点对(s,t)之间的最短路数量我们已经求好了,而这些最短路中经过点v的最短路数量,显然可以依据分步乘法计数原理,通过 (dp[s][v] * dp[v][t]) 计算出.此外,额外规定,如果当前点不在最短路中,这个数是0.在这两个数量都计算出后,我们只需要按照给定的这个式子除一下,最后全部累加起来即可.

最后注意一下,最短路的数量可能会超过int类型的范围,所以这里我们需要用long long类型来保存.

参考代码

时间复杂度: (O(N^3 + M)) (计入输入使用时间)

空间复杂度: (O(N^2))

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(n, 0x3f3f3f3f)); // Floyd最好直接用邻接矩阵
    vector<vector<i64>> dp(n, vector<i64>(n)); // 维护两条边之间最短路的数量,注意会爆int,要开成long long

    // 输入各边
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; // 下标转为从0开始
        b--;
        g[a][b] = c;
        g[b][a] = c; // 无向边
        dp[a][b] = 1;
        dp[b][a] = 1; // 无向边
    }

    // Floyd
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] > g[i][k] + g[k][j]) { // 当前点可用来松弛
                    g[i][j] = g[i][k] + g[k][j]; // 松弛
                    dp[i][j] = dp[i][k] * dp[k][j]; // 利用乘法原理重新计算最短路数量
                } else if (g[i][j] == g[i][k] + g[k][j]) { // 当前点如果用来松弛,与原本效果一样,是另一条最短路
                    dp[i][j] += dp[i][k] * dp[k][j]; // 利用乘法原理更新最短路数量
                }
            }
        }
    }

    // 计算题目要求的那个公式的结果
    for (int v = 0; v < n; v++) { // 自变量
        double ans = 0;

        // 计算求和式
        for (int s = 0; s < n; s++) {
            for (int t = 0; t < n; t++) {
                if (s != t && s != v && t != v && g[s][t] == g[s][v] + g[v][t]) { // 当前点是最短路的一部分
                    ans += (double)(dp[s][v] * dp[v][t]) / dp[s][t];
                }
            }
        }
        cout << fixed << setprecision(3) << ans << "
"; // 输出样例是三位小数,所以这里我保留了三位小数
    }

    return 0;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德