P2047 [NOI2007] 社交网络题解

_Ayanami_Rei_ · 2024-01-19 09:29:32 · 题解

这是本蒟蒻第一次发题解，还有很多不足之处，望请教！

题目传送门：P2047 [NOI2007] 社交网络

题意分析

这道题看似十分的绕，实则十分的简单：对于点 v 的重要性，就是 v 在所有不同于 s、t 两点间最短路上被经过的次数与 s、t 两点之间的最短路总数目之比的和~~感觉用文字表述比公式更难看懂~~。

解题思路

首先大家看到题面，就都可以感受到这是一个多源的最短路问题，加上数据范围里的 n \le 100，都可以立马察觉到这应该是要用 Floyd 算法。那么对于最短路的条数以及点 v 在 s、t 的最短路里出现的次数可以用一个三维的 sum_{s,t,v} 存储。sum_{s,t,v} 表示点 v 在 s 到 t 的最短路上的重要程度。因为不存在点 0，所以我用 sum_{s,t,0} 来存储从 s 到 t 的最短路条数。那么 sum 该怎么初始化以及怎么更新呢？

初始化

在最开始全部初始化为 0，存边时，便将 sum_{a,b,0} 初始化为 1，表明 a 与 b 之间有一条边连接，且那条边是 a、b 间目前的最短路，因为边上除起点重点上外并无其他点，因此 sum_{a,b,i},\ i\in\lbrack1,n\rbrack 全部赋值为 0。

代码如下：

memset (dis, 0x3f, sizeof dis);
memset (sum, 0, sizeof sum);
scanf ("%d %d", &n, &m);
for (int i = 1;i <= n; ++i) {
    dis[i][i] = 0;
}
for (int i = 1;i <= m; ++i) {
    int a, b, c;
    scanf ("%lld %lld %lld", &a, &b, &c);
    dis[a][b] = dis[b][a] = c;
    ++sum[a][b][0], ++sum[b][a][0];
}

更新

不难看出，当有一个点 k 使得 dis_{i,j} \le dis_{i,k} + dis_{k,j} 时就需要更新 sum_{i,j,u},u\in\lbrack1,n\rbrack。

1.dis_{i,k}+dis_{k,j}<dis_{i,j} 时

更新 dis_{i,j}，并将 sum_{i,j,u},u\in\lbrack 1,n\rbrack 全部赋值为 0，因为最短路都换了，那就跟那条换之前的路径上的点没关系了。然后根据乘法原理可得 sum_{i,j,u} = sum_{i,k,u} \times sum_{k,j,0}（i 到 j 中 u 点出现的次数是 i 到 k 上出现的次数乘上 k 到 j 的最短路数），看下图也许能帮助各位理解。

然而，因重要程度不算起点终点，所以当 u = k 时，sum_{i,k,k}=0，因而 sum_{i,j,k} = sum_{i,k,k} \times sum_{k,j,0} = 0，显然这是不对的，所以要对 sum_{i,j,k} 进行特殊处理：sum_{i,j,k}=sum_{i,k,0}\times sum_{k,j,0}（终点 k 出现的次数就是最短路的条数）。

同样的，对于在 k 到 j 上的 u 也有同样的操作：sum_{i,j,u}=sum_{i,k,u}\times sum_{k,j,0}。图如下。

更新完路径上的点的重要值，便要更新最短路的条数了，同样根据乘法原理易得：sum_{i,j,0}=sum_{i,k,0}\times sum_{k,j,0}。

代码如下：

if (dis[i][j] > dis[i][k] + dis[k][j]) {
    dis[i][j] = dis[i][k] + dis[k][j];
    fill (sum[i][j], sum[i][j] + 1 + n, 0);
    for (int u = 1;u <= n; ++u) {
        if (i == u || u == j) continue;
        sum[i][j][u] += sum[i][k][u] * sum[k][j][0];
        sum[i][j][u] += sum[k][j][u] * sum[i][k][0];
    }
    sum[i][j][k] += sum[i][k][0] * sum[k][j][0];
    sum[i][j][0] += sum[i][k][0] * sum[k][j][0];
}

2.dis_{i,k} + dis_{k,j} = dis_{i,j} 时

对于这一种情况，与上一种处理方法是很相似的，只是不用清空 sum_{i,j,u},\ u \in\lbrack1,n\rbrack。因此代码如下：

if (dis[i][j] == dis[i][k] + dis[k][j]) {
    for (int u = 1;u <= n; ++u) {
        if (i == u || u == j) continue;
        sum[i][j][u] += sum[i][k][u] * sum[k][j][0];
        if (u != k) {
            sum[i][j][u] += sum[k][j][u] * sum[i][k][0];
        }
    }
    sum[i][j][k] += sum[i][k][0] * sum[k][j][0];
    sum[i][j][0] += sum[i][k][0] * sum[k][j][0];
}

输出

最后这一段没有什么好讲了的，根据题意就可以轻而易举地得出下面这条公式：

\large I(k)=\sum\limits^{n} \limits_{i=1, j=1}sum_{i,j,k}\div sum_{i,j,0}

代码实现如下：

for (int k = 1; k <= n; ++k) {
    double ans = 0.0;
    for (int i = 1; i <= n; ++i) {
        if (i == k) continue;
        for (int j = 1; j <= n; ++j) {
            if (j == k) continue;
            if (sum[i][j][0] != 0)
                ans += sum[i][j][k] * 1.0 / sum[i][j][0];
        }
    }
    printf ("%.3f\n", ans);
}

AC代码

将上述代码加以整合简化，便可以得出下面的AC代码：

#include <iostream>
#include <cstring>
using namespace std;
#define int long long
// 两点间最短路数目不超过1e10，记得开long long
int dis[101][101], sum[101][101][101], n, m;

signed main () {
    memset (dis, 0x3f, sizeof dis);
    const int INF = dis[0][0];
    scanf ("%d %d", &n, &m);
    for (int i = 1;i <= n; ++i) {
        dis[i][i] = 0;
    }
    for (int i = 1;i <= m; ++i) {
        int a, b, c;
        scanf ("%lld %lld %lld", &a, &b, &c);
        dis[a][b] = dis[b][a] = c;
        ++sum[a][b][0], ++sum[b][a][0];
    }
    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) continue;
                if (dis[i][j] > dis[i][k] + dis[k][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
              // 这里先不做更改，对dis赋值以进入下面的if来更新
                    fill (sum[i][j], sum[i][j] + 1 + n, 0);
                }
                if (dis[i][j] == dis[i][k] + dis[k][j]) {
                    for (int u = 1;u <= n; ++u) {
                        if (i == u || u == j) continue;
                        sum[i][j][u] += sum[i][k][u] * sum[k][j][0];
                        sum[i][j][u] += sum[k][j][u] * sum[i][k][0];
                    }
                    sum[i][j][k] += sum[i][k][0] * sum[k][j][0];
                    sum[i][j][0] += sum[i][k][0] * sum[k][j][0];
                }
            }
        }
    }
    for (int k = 1; k <= n; ++k) {
        double ans = 0.0;
        for (int i = 1; i <= n; ++i) {
            if (i == k) continue;
            for (int j = 1; j <= n; ++j) {
                if (j == k) continue;
                if (sum[i][j][0] != 0)
              // 除数不能为0
                    ans += sum[i][j][k] * 1.0 / sum[i][j][0];
            }
        }
        printf ("%.3f\n", ans);
    }
    return 0;
}

鸣谢

在这片题解的最后，我想感谢一下同一机房的两位大佬 _Kaedehara_Kazusha_ 和 Tzy090420，给了本蒟蒻众多帮助来A这道题（~~没错，我就菜到这题都能卡我一下~~）！！！

P2047 [NOI2007] 社交网络 题解