【Floyd】BZOJ1491: [NOI2007]社交网络

Description

Solution

n<=100自然联想Floyd

设两个数组d[n][n]存最短距离，t[n][n]存最短路径条数

更新d的时候顺便更新t，乘法原理

 if(d[i][j]>d[i][k]+d[k][j]){
     d[i][j]=d[i][k]+d[k][j];
     t[i][j]=t[i][k]*t[k][j];
 }
 else if(d[i][j]==d[i][k]+d[k][j])
     t[i][j]+=t[i][k]*t[k][j];

再统计答案

 if(d[i][j]==d[i][k]+d[k][j])
     c[k]+=(double)(t[i][k]*t[k][j])/t[i][j];

感觉Floyd也就能做这些事。。

Code

 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #define ll long long
 const int maxn=;

 ll d[maxn][maxn],t[maxn][maxn];
 int n,m;
 double c[maxn];

 int main(){
     scanf("%d%d",&n,&m);
     int u,v,w;
     memset(d,/,sizeof(d));
     for(int i=;i<=n;i++)
         d[i][i]=,t[i][i]=;

     for(int i=;i<=m;i++){
         scanf("%d%d%d",&u,&v,&w);
         if(w<d[u][v]){
             d[u][v]=d[v][u]=w;
             t[u][v]=t[v][u]=;
         }
         else if(w==d[u][v]){
             t[u][v]++;
             t[v][u]++;
         }
     }

     for(int k=;k<=n;k++)
         for(int i=;i<=n;i++)
             for(int j=;j<=n;j++)if(i!=j&&i!=k&&j!=k){
                 if(d[i][j]>d[i][k]+d[k][j]){
                     d[i][j]=d[i][k]+d[k][j];
                     t[i][j]=t[i][k]*t[k][j];
                 }
                 else if(d[i][j]==d[i][k]+d[k][j])
                     t[i][j]+=t[i][k]*t[k][j];
             }

     memset(c,,sizeof(c));
     for(int i=;i<=n;i++)
         for(int j=;j<=n;j++)
             for(int k=;k<=n;k++)if(i!=j&&i!=k&&j!=k){
                 if(d[i][j]!=d[i][k]+d[k][j]) continue;
                 c[k]+=(double)t[i][k]*t[k][j]/t[i][j];
             }

     for(int i=;i<=n;i++)
         printf("%.3lf\n",c[i]);
     return ;
 }