P2047 [NOI2007]社交网络

Love The Way You Lie 2023-06-04 08:53 17阅读 0赞

[**题目链接**][Link 1]

**这道题是一道图论题，非常显然，题中的目的非常明显，就是统计最短路并求和。n<=100，一看到这个数据范围，就可以想到n^3的Floyd，但是考虑如何来求出最短路的个数？**

**一开始我想的是Floyd预处理最短路，然后再dijkstra统计最短路个数，因为我只会dijkstra的最短路计数。由于dijkstra是单源最短路，所以这样做的复杂度又多了一个n。**

**其实用Floyd就可以了，再求最短路的时候可以顺便统计最短路的个数。统计最短路其实就可以用到乘法原理解决。**

**设dis\[i\]\[j\]为i->j的最短路，way\[i\]\[j\]为i->j的最短路条数，有一个中间点k。**

**分类讨论:**

--------------------

**1.如果dis\[i\]\[j\]>dis\[i\]\[k\]+dis\[k\]\[j\]。这样就要求我们更新最短路，而从i->j的最短路条数就是way\[i\]\[k\]\*way\[k\]\[j\]**

**2.如果当前路径与最短路距离相等，那么只需要在原基础上累加way\[i\]\[k\]\*way\[k\]\[j\]的值即可。**

--------------------

**然后按题上的公式做就可以了。注意要统计路径时要开longlong，题上也给了提示。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    const int N=550;
    const int inf=88888888;
    int mp[N][N];
    long long way[N][N]; 
    int n,m;
    int x,y,v;
    double sum[maxn];
    void floyd(){
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(i!=k&&i!=j&&k!=j){
                        if(mp[i][j]>mp[i][k]+mp[k][j]){
                            mp[i][j]=mp[i][k]+mp[k][j];
                            way[i][j]=way[i][k]*way[k][j];
                        } 
                        else if(mp[i][j]==mp[i][k]+mp[k][j]) way[i][j]+=way[i][k]*way[k][j];
                    }
                }
            }
        }
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) mp[i][j]=inf;
        }
        for(int i=1;i<=n;i++) mp[i][i]=0;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&v);
            mp[x][y]=mp[y][x]=v;
            way[x][y]=way[y][x]=1;
        }
        floyd();
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){    
                    if(i!=j&&j!=k&&i!=k){
                        long long ljb=way[i][k]*way[k][j];
                        if(mp[i][j]==mp[i][k]+mp[k][j]) sum[k]+=(ljb*1.000)/way[i][j];
                    }
                }
            }
        }
        for(int i=1;i<=n;i++) printf("%.3lf\n",sum[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11614579.html

[Link 1]: https://www.luogu.org/problem/P2047
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/ff0d085b05f54083ab83f31254586d8f.png