[NOI2007 day1 社交网络]floyed变形

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1491

【算法分析】

就是利用floyed求最短路。然后加多一个数组表示num[i][j]表示从i到j的最短路的数目。

然后在松弛的地方因为乘法原理，应当变成num[i][k]*num[k][j]，相等的话要加上方案。

最后统计一下就好了。

【其它】1A

【CODE】

#include using namespace std;
int n,m;
int d[122][122];
long long num[122][122];

void input(){
    memset(d,50,sizeof(d));
    memset(num,0,sizeof(num));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        d[x][y]=w;
        d[y][x]=w;
        num[x][y]=1;
        num[y][x]=1;
    }   
}   

void floyed(){
    int i,j,k;
    for (k=1;k<=n;k++)
      for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
          if (i!=j && j!=k && i!=k){
              if (d[i][k]+d[k][j]                  d[i][j]=d[i][k]+d[k][j];
                  num[i][j]=num[i][k]*num[k][j];
              }   
              else if (d[i][k]+d[k][j]==d[i][j])
                  num[i][j]+=num[i][k]*num[k][j];
          }   
}   

void output(){
    int i,j,k;
    for (k=1;k<=n;k++){
        double ans=0;
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
            if (i!=j && j!=k && i!=k && d[i][j]==d[i][k]+d[k][j])
                ans+=num[i][k]*num[k][j]*1.0/num[i][j];
        printf("%.3lfn",ans);
    }   
}   

int main(){
    freopen("network.in","r",stdin);
    freopen("network.out","w",stdout);
    input();
    floyed();
    output();
}