bzoj1491 luogu2047 [NOI2007]社交网络

叁歲伎倆 2021-10-18 16:20 322阅读 0赞

[https://www.lydsy.com/JudgeOnline/problem.php?id=1491][https_www.lydsy.com_JudgeOnline_problem.php_id_1491]

一开始想用最短路图做，后来发现可以直接floyd

floyd算最短路距离的同时统计最短路方案数

一开始纠结这样会不会算重，但理解清楚floyd的本质就能明白了

假如某层循环中$dis\_\{i,j\}==dis\_\{i,k\}+dis\_\{k,j\}$（枚举时一定要满足$i\\not=j 且 j\\not=k 且 i\\not=k$）

那么方案数$f\_\{i,j\}$中肯定不包括经过了点$k$的方案

#include<bits/stdc++.h>
    using namespace std;
    const int N=105;
    int n,m;
    int dis[N][N];
    long long f[N][N];
    double ans[N];
    int main()
    {
        scanf("%d%d",&n,&m);
        memset(dis,0x3f,sizeof(dis));
        for(int i=1;i<=n;++i) dis[i][i]=0,f[i][i]=1;
        for(int i=1;i<=m;++i)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            dis[u][v]=dis[v][u]=w;
            f[u][v]=f[v][u]=1;
        }
        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)
                {
                    if(dis[i][j]==dis[i][k]+dis[k][j])
                        f[i][j]+=f[i][k]*f[k][j];
                    if(dis[i][j]>dis[i][k]+dis[k][j])
                        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]),
                        f[i][j]=f[i][k]*f[k][j];
                }
        /*for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)cout<<dis[i][j]<<" ";
            cout<<endl;
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j) cout<<f[i][j]<<" ";
            cout<<endl;
        }*/
        for(int k=1;k<=n;++k)
            for(int i=1;i<=n;++i)
            if(i!=k)
                for(int j=1;j<=n;++j)
                if(j!=k && j!=i)
                {
                    if(dis[i][j]==dis[i][k]+dis[k][j] && f[i][j]!=0)
                        ans[k]+=(double)(f[i][k]*f[k][j])/(double)f[i][j];
                }
        for(int i=1;i<=n;++i) printf("%.3lf\n",ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/w19567/p/11322270.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_1491]: https://www.lydsy.com/JudgeOnline/problem.php?id=1491