社交网络-最短路统计
分析:题目比较繁琐,提取完有用信息之后就是一个最短路统计。唯一的难点是经过点v的最短路统计。我们可以转换成C(s,v)*C(v,t)
代码如下:
#include<stdio.h> #define inf 100000001 double f[101][101]; double g[101][101]; double min(double x,double y){return x<y?x:y;} double max(double x,double y){return x>y?x:y;} int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i!=j) f[i][j]=inf; } } for(int i=1;i<=m;i++) { int x,y; double z; scanf("%d%d%lf",&x,&y,&z); if(x==y) continue; f[x][y]=min(f[x][y],z); f[y][x]=min(f[y][x],z); g[x][y]=g[y][x]=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][j]>f[i][k]+f[k][j]) { f[i][j]=f[i][k]+f[k][j]; g[i][j]=g[i][k]*g[k][j]; continue; } if(f[i][j]==f[i][k]+f[k][j]) g[i][j]+=g[i][k]*g[k][j]; } for(int v=1;v<=n;v++) { double sum=0; for(int s=1;s<=n;s++) for(int t=1;t<=n;t++) { if(v==s||v==t||s==t) continue; if(f[s][v]+f[v][t]==f[s][t]) sum+=(1.0*g[s][v]*g[v][t])/g[s][t]; } printf("%.3lf ",sum); } }