【题目来源】
洛谷：[P2047 NOI2007] 社交网络 - 洛谷
【题目描述】
在社交网络（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\) 的最短路的数目；则定义：
为结点 \(v\) 在社交网络中的重要程度。为了使 \(I(v)\) 和 \(C_{s,t}(v)\) 有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。现在给出这样一幅描述社交网络的加权无向图，请你求出每一个结点的重要程度。
【输入】
输入第一行有两个整数 \(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
【解题思路】
【算法标签】
《洛谷 P2047 社交网络》 #图论# #最短路# #NOI# #2007#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型
const int N = 105; // 最大节点数int n, m; // n: 节点数, m: 边数
int u, v, w; // 临时变量：边的两端点和权值
int dist[N][N]; // 存储最短路径长度
int num[N][N]; // 存储最短路径数量signed main()
{cin >> n >> m;// 初始化距离矩阵（初始为无穷大）memset(dist, 0x3f, sizeof(dist));// 输入边信息并初始化for (int i = 1; i <= m; i++){cin >> u >> v >> w;dist[u][v] = w; // 存储边权num[u][v] = 1; // 初始化路径数为1dist[v][u] = w; // 无向图，双向存储num[v][u] = 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 (k == i || i == j || k == j)continue;// 找到更短路径if (dist[i][j] > dist[i][k] + dist[k][j]){dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短距离num[i][j] = num[i][k] * num[k][j]; // 更新路径数量}// 找到等长路径else if (dist[i][j] == dist[i][k] + dist[k][j]){num[i][j] += num[i][k] * num[k][j]; // 累加路径数量}}}}// 计算每个节点的中介中心性for (int k = 1; k <= n; k++) // 对于每个节点k{double ans = 0; // 存储k的中介中心性// 遍历所有点对(i,j)for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){// 跳过无效情况if (k == i || i == j || j == k)continue;// 如果k在i到j的最短路径上if (dist[i][j] == dist[i][k] + dist[k][j]){// 计算贡献值并累加ans += (1.0 * num[i][k] * num[k][j]) / num[i][j];}}}// 输出结果（保留3位小数）printf("%.3lf\n", ans);}return 0;
}
【运行结果】
4 4
1 2 1
2 3 1
3 4 1
4 1 1
1.000
1.000
1.000
1.000