「BZOJ1491」[NOI2007] 社交网络
Description
Input
Output
输出文件包括n 行，每行一个实数，精确到小数点后3 位。第i 行的实数表 示结点i 在社交网络中的重要程度。
Sample Input
4 4
1 2 1
2 3 1
3 4 1
4 1 1
1 2 1
2 3 1
3 4 1
4 1 1
Sample Output
1.000
1.000
1.000
1.000
1.000
1.000
1.000
HINT
为1
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m; double mp[101][101]; double a[101][101]; double ans[101]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=1e15; int x,y;double z; for(int i=1;i<=m;i++) { scanf("%d%d%lf",&x,&y,&z); mp[x][y]=mp[y][x]=z; a[x][y]=a[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(mp[i][k]+mp[k][j]<mp[i][j]){mp[i][j]=mp[i][k]+mp[k][j];a[i][j]=0;} if(mp[i][k]+mp[k][j]==mp[i][j])a[i][j]+=a[i][k]*a[k][j]; } for(int i=1;i<=n;i++)a[i][i]=0; for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(mp[i][k]+mp[k][j]==mp[i][j]&&a[i][j]>0) ans[k]+=a[i][k]*a[k][j]/a[i][j]; } for(int i=1;i<=n;i++)printf("%.3lf\n",ans[i]); return 0; } |
Subscribe
计数器 9863304
OI 课件=>
OI 课件=>