题解

本题使用Floyd算法 + 最短路计数求解社交网络中心性问题。

算法思路：

1. Floyd求最短路：

   • f[i][j]：点 $i$ 到点 $j$ 的最短距离
   • g[i][j]：从 $i$ 到 $j$ 的最短路数量
   • 初始化：直接相连的边 $f[a][b] = c$，$g[a][b] = 1$

2. 最短路计数：

   • 在Floyd更新最短路时，同时维护最短路数量
   • 如果找到更短的路径：
     • $f[i][j] = f[i][k] + f[k][j]$
     • $g[i][j] = g[i][k] \times g[k][j]$（路径数量相乘）
   • 如果路径长度相同：
     • $g[i][j] += g[i][k] \times g[k][j]$（累加新路径）

3. 中心性计算（Betweenness Centrality）：

   • 对于节点 $k$，计算其重要性 $I[k]$
   • 枚举所有点对 $(i, j)$，满足 $i \neq j \neq k$
   • 如果 $k$ 在 $i$ 到 $j$ 的最短路上（$f[i][k] + f[k][j] = f[i][j]$）：
     • 贡献：$I[k] += \frac{g[i][k] \times g[k][j]}{g[i][j]}$

4. 公式理解：

   • $g[i][k] \times g[k][j]$：经过 $k$ 的最短路径数
   • $g[i][j]$：所有最短路径总数
   • 比值表示 $k$ 在 $i$ 到 $j$ 的最短路中的"重要程度"

5. 输出格式：

   • 对每个节点，输出保留3位小数的中心性值

时间复杂度：$O(n^3)$

这是图论中经典的中心性（Centrality）计算问题，用于衡量节点在网络中的重要性。

#include<bits/stdc++.h>
using namespace std;
const int N=102;
typedef long long ll;
int n,m,a,b,c;
ll f[N][N],g[N][N];
double I[N];
int main(){
//	freopen("filename.in","r",stdin);
//	freopen("filename.out","w",stdout);
	memset(f,0x3f,sizeof f);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		f[a][b]=f[b][a]=c;
		g[a][b]=g[b][a]=1;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(f[i][k]+f[k][j]<f[i][j]){
					f[i][j]=f[i][k]+f[k][j];
					g[i][j]=g[i][k]*g[k][j];
				}
				else if(f[i][k]+f[k][j]==f[i][j]) g[i][j]+=g[i][k]*g[k][j];
			}
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i!=j && i!=k && k!=j && f[i][k]+f[k][j]==f[i][j]) I[k]+=1.0*g[i][k]*g[k][j]/g[i][j];
			}
		}
	}
	for(int k=1;k<=n;k++) printf("%.3lf\n",I[k]);
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}