acwing-386. 社交网络

发表于 分类于 阅读次数： Waline： 本文字数： 391 阅读时长 ≈ 1 分钟

考点

  • 最短路
  • Floyd的路径

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 50;
int n, m;
ll d[maxn][maxn], c[maxn][maxn];
double ans[maxn];

int main() {
  cin >> n >> m;
  memset(d, 0x3f, sizeof(d));
  for (int u, v, w, i = 1; i <= m; ++i) {
    cin >> u >> v >> w;
    c[u][v] = c[v][u] = 1, d[u][v] = d[v][u] = w;
  }
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (i != j && i != k && j != k) {
          if (d[i][j] > d[i][k] + d[k][j]) {
            c[i][j] = c[i][k] * c[k][j];
            d[i][j] = d[i][k] + d[k][j];
          } else if (d[i][j] == d[i][k] + d[k][j]) {
            c[i][j] += c[i][k] * c[k][j];
          }
        }
  for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        if (i != j && i != k && j != k && d[i][j] == d[i][k] + d[k][j])
          ans[k] += (double)c[i][k] * c[k][j] / c[i][j];
  for (int i = 1; i <= n; ++i) printf("%.3lf\n", ans[i]);
  return 0;
}

思路

注意审题，本题中i, j, k即两端点和中间点都不能相同！

所以没有d[i][i] = 0, c[i][i] = 1的常规初始化，且所有的最短路更新和次数记录也必须都在i != j && i != k && j != k的条件下进行！

点k是否经过(i, j)的最短路，判断d[i][j] == d[i][k] + d[k][j]即可

如图所示，假设k是(i, j)的中间点，k0是(i, k)的中间点，那么有：

  • d[i][j] = d[i][k] + d[k][j]，而d[i][k] = d[i][k0] + d[k0][k]
  • 后式代入前式，显然有d[i][j] = d[i][k0] + d[k0][k] + d[k][j] = d[i][k0] + d[k0][j]