本文主要是介绍P2047 [NOI2007] 社交网络,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Portal.
观察到数据范围 n ≤ 100 n\leq 100 n≤100,考虑用 Floyd。
在 Floyd 更新最短路的过程中,如果以当前结点为中转点的路径更新过,那么可以累加答案;否则,更新最短路径并重置答案。
统计答案时,枚举中转点判断累加即可。
#include <bits/stdc++.h>
using namespace std;
#define int long longint f[105][105],C[105][105];
double I[105];signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=1e9;for(int i=1,a,b,c;i<=m;i++) cin>>a>>b>>c,f[a][b]=f[b][a]=c,C[a][b]=C[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(i!=j&&j!=k&&i!=k){if(f[i][j]==f[i][k]+f[k][j]) C[i][j]+=C[i][k]*C[k][j];else if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j],C[i][j]=C[i][k]*C[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&&j!=k&&k!=i&&f[i][j]==f[i][k]+f[k][j]) I[k]+=((double)C[i][k]*C[k][j])/C[i][j];for(int i=1;i<=n;i++) printf("%.3lf\n",I[i]);return 0;
}
这篇关于P2047 [NOI2007] 社交网络的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!