题解 P2047 【[NOI2007]社交网络】

· · 题解

因为题目中的公式会求到每一个起点s到终点t，且n只有100，所以我们就想到了Floyd

要求求s到t的路径条数，可以在Floyd的同时统计条数，在建边的时候将u到v条数设为1

在Floyd的时候我们如何更新条数呢？其实很简单。

dis[i][j]从i点到j点的最短路
sum[i][j]从i点到j点的最短路条数
如果dis[i][k]+dis[k][j]等于dis[i][j]那么sum[i][j]的条数会增加（长短一样），根据乘法原理，sum[i][j]加上sum[i][k]*sum[k][j]
如果小于的话，dis要更新，sum变成sum[i][k]*sum[k][j]

最后如何统计呢?

每一个k点，枚举每一个i和j，如果dis[i][k]+dis[k][j]等于dis[i][j]，那么就加上sum[i][k]*sum[k][j]除以sum[i][j]（i、j的总条数和经过k的条数）

注意：dis最初要赋一个足够大的值，sum最初是0，ans因为要精度，所以用double

code: 
#include <cstdio>
int n,m,u,v;
double ans,dis[101][101],sum[101][101];
int read(){
    char ch=getchar();int res=0,w=1;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {res=res*10+ch-'0';ch=getchar();}
    return res*w;
}
int main(){
    n=read();m=read();
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++) dis[i][j]=0x3fffffff;
    while(m--) {u=read();v=read();dis[u][v]=dis[v][u]=read();sum[u][v]=sum[v][u]=1;}
    for(register int k=1;k<=n;k++)
        for(register int i=1;i<=n;i++)
            for(register int j=1;j<=n;j++)
                if(i!=j&&j!=k&&i!=k)//Floyd
                {
                    if(dis[i][k]+dis[k][j]==dis[i][j]) sum[i][j]+=sum[i][k]*sum[k][j];//等于
                    else if(dis[i][k]+dis[k][j]<dis[i][j]) {dis[i][j]=dis[i][k]+dis[k][j];sum[i][j]=sum[i][k]*sum[k][j];}//小于
                }
    for(register int k=1;k<=n;k++)///统计
    {
        ans=0;
        for(register int i=1;i<=n;i++)
            for(register int j=1;j<=n;j++)
                if(j!=i&&k!=i&&j!=k&&dis[i][k]+dis[k][j]==dis[i][j])/*判断*/ ans+=sum[i][k]*sum[k][j]/sum[i][j];//公式
        printf("%.3lf\n",ans);//输出
    }           
    return 0;
}