洛谷2047 [NOI2007]社交网络

题意

令 $C_{s,t}$ 表示从 $s$ 到 $t$ 的不同的最短路的数目，$C_{s,t}(v)$ 表示经过 $v$ 从 $s$ 到 $t$ 的最短路的数目；则定义：

$$ I(v)=\sum_{s \ne v,t\ne v} \frac{C_{s,t}(v)}{C_{s,t}}$$

其中点数 $n\le 100$ ，边数 $m\le 4500$ 。

题解

$n\le 100$ ，又要统计所有节点的情况，很显然是 $\text{floyd}$ 。

对于 $C_{s,t}(v)$ ，可以通过枚举 $s,t,v$ ，并判断 $v$ 是否在 $s,t$ 最短路上，即 $\text{f[s][v]}+\text{f[v][t]}=\text{f[s][t]}$ 。

对于 $C_{s,t}$ ，可以在 $\text{floyd}$ 的过程中顺便求出。

用 $cnt[i][j]$ 表示 $i\rightarrow j$ 的最短路条数。如果最短路更新了就重置；如果当前路径和最短路相等就加上。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,a,b,c,dis[105][105],cnt[105][105];

signed main()
{
    memset(dis,0x3f,sizeof(dis));
    n=read(); m=read();
    for (ll i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        dis[a][b]=dis[b][a]=c;
        cnt[a][b]=++cnt[b][a];
    }
    for (ll k=1;k<=n;k++)
    {
        for (ll i=1;i<=n;i++)
        {
            for (ll j=1;j<=n;j++)
            {
                if (dis[i][j]<dis[i][k]+dis[k][j]) continue;
                if (dis[i][j]>dis[i][k]+dis[k][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                    cnt[i][j]=cnt[i][k]*cnt[k][j];
                }
                else cnt[i][j]+=cnt[i][k]*cnt[k][j];
            }
        }
    }
    for (ll k=1;k<=n;k++)
    {
        double v=0;
        for (ll i=1;i<=n;i++)
        {
            if (i==k) continue;
            for (ll j=1;j<=n;j++)
            {
                if (j==k || i==j) continue;
                if (dis[i][k]+dis[k][j]!=dis[i][j]) continue;
                v+=1.0*cnt[i][k]*cnt[k][j]/cnt[i][j];
            }
        }
        printf("%.3f\n",v);
    }
    return 0;
}