题解 P2047 【社交网络】

· · 题解

Solution：

这道题目思路比较简单：

1.预处理出最短路，因为范围小，采用弗洛伊德算法预处理

2.处理出从i到j点中间最短路条数[这一步算是整个代码中的精华，也是最难的的一部分了吧（我认为的最难，蒟蒻哎ORZ）]

3.就是计算答案啦啦

然后呢，这题就是思考那个奇奇怪怪的计算式子了

I(v)=∑(s<>v,t<>v)Cs,t(v) / Cs,t

A.首先呢解释下这个式子：

　　a.(s<>v,t<>v) s!=v&&t!=v 很好理解吧

　　b.Cs,t(v) 是所有s到t的最短路中，经过v的条数

c.Cs,t 是从s到t的最短路条数

B.然后思路步骤一很简单，就不说了，不清楚可以自行问度娘

C.步骤二的方法有很多我知道有两种

a.在弗洛伊德求最短路时同时更新路径条数[我用的这种，真的好容易打%%%想出来这种方法的人]

for(int k=1;k<=n;k++)//枚举中间点
    for(int i=1;i<=n;i++)//枚举开头
    for(int j=1;j<=n;j++)//枚举结尾
    {
        if(dis[i][k]==INF&&dis[k][j]==INF)continue;//INF是初始化定义的最大值
        if(dis[i][j]>dis[i][k]+dis[k][j])//满足更新条件
        {
            dis[i][j]=dis[i][k]+dis[k][j];//更新最短路径的值
            edge[i][j]=edge[i][k]*edge[k][j];//更新最短路径条数
            continue;
        }
        if(dis[i][j]==dis[i][k]+dis[k][j])//和已算出来的最短路长度相等
        {edge[i][j]+=edge[i][k]*edge[k][j];}//累加路径条数
    }//dis  长度    edge   条数

b.这种方法见我的另一篇博客，里面讲的很详细，这个代码打的重点在 求入度次数和拓扑排序

D.步骤三计算答案，这个重点就是在处理Cs,t(v)

1.dis[s][t]=dis[s][v]+dis[v][t] 这个很好理解吧 如果S-V的最短距离加上V-T的最短距离等于S-T的最短距离 那么V一定在S-T的最短路上

2.所以 Cs,t(v)= S-V的路径条数*V-T的路径条数

3.另外 要枚举所有的 S - T 注意式子的∑(s<>v,t<>v)

4.应该没了 顺便贴下我这部分的代码

for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
        {
            if(i==j||j==k||i==k)continue;
            if(dis[j][i]+dis[i][k]==dis[j][k])
                ans[i]+=(1.0*edge[j][i]*edge[i][k])/edge[j][k];
        }
    }

最后，还要用拓扑排序的同学注意一点就是：重边，某点的入度被减为0[每有一条边指向点K，点K入度数减一，更新到K点路径条数]才能入队列，向下传递记录条数的数值。否则来一条边向下传一次，会使条数计算错误。[悲伤地是，我没改对这个注意的点，还是只有60分 ORZ][另一种方法过了]

贴一下整体AC代码吧

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
int n,m;
LL INF;
LL dis[100+10][100+10],edge[100+10][100+10];
double ans[100+10];
int main()
{
    freopen("bestlink.in","r",stdin);
    freopen("bestlink.out","w",stdout);
    n=read();m=read();
    memset(dis,0x7f,sizeof(dis));
    memset(edge,0,sizeof(dis));
    INF=dis[1][1];
    for(int i=1;i<=m;i++)
    {
        LL x,y,z;
        x=read();y=read();z=read();
        dis[x][y]=dis[y][x]=z;
        edge[x][y]=edge[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(dis[i][k]==INF&&dis[k][j]==INF)continue;
        if(dis[i][j]>dis[i][k]+dis[k][j])
        {
            dis[i][j]=dis[i][k]+dis[k][j];
            edge[i][j]=edge[i][k]*edge[k][j];
            continue;
        }
        if(dis[i][j]==dis[i][k]+dis[k][j])
        {edge[i][j]+=edge[i][k]*edge[k][j];}
    }
/*    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)cout<<i<<' '<<j<<' '<<edge[i][j]<<endl;*/
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
        {
            if(i==j||j==k||i==k)continue;
            if(dis[j][i]+dis[i][k]==dis[j][k])
                ans[i]+=(1.0*edge[j][i]*edge[i][k])/edge[j][k];
        }
    }
    for(int i=1;i<=n;i++)
        printf("%0.3f\n",ans[i]);
    return 0;
}

不要脸的贴上自己的博客