acwing-349. 黑暗城堡

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

考点

  • 最短路径生成树

题解

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
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;
const ll mod = (1ll << 31) - 1;
ll ans = 1;
int n, m, d[maxn], a[maxn][maxn];
bool v[maxn];

// 邻接矩阵的暴力Dijkstra
void dijkstra() {
  memset(d, 0x3f, sizeof(d));
  d[1] = 0;
  for (int k = 1; k < n; ++k) {
    int x = 0;
    for (int i = 1; i <= n; ++i)
      if (!v[i] && (x == 0 || d[x] > d[i])) x = i;
    v[x] = 1;
    for (int y = 1; y <= n; ++y) d[y] = min(d[y], a[x][y] + d[x]);
  }
}

void prim() {
  memset(v, 0, sizeof(v));
  v[1] = 1;
  for (int k = 1; k <= n; ++k) {
    int x = 0, cnt = 0;
    for (int i = 1; i <= n; ++i)
      if (!v[i] && (x == 0 || d[x] > d[i])) x = i;
    for (int y = 1; y <= n; ++y)
      if (v[y] && d[x] == d[y] + a[x][y]) ++cnt;
    v[x] = 1;
    ans = (ans * cnt) % mod;
  }
}

int main() {
  cin >> n >> m;
  memset(a, 0x3f, sizeof(a));
  for (int x, y, z, i = 1; i <= m; i++) {
    cin >> x >> y >> z;
    a[x][y] = a[y][x] = min(a[x][y], z);
  }
  dijkstra(), prim();
  cout << ans << endl;
  return 0;
}

思路

最短路径生成树的模板题。

先用Dijkstra算法求出1号房间到每个房间x的单源最短路，保存到dist[x]。

把树形城堡看作以1为根的有根树后，

若x是y的父节点，x，y之间的通道长度为z，则应该有：dist[y] = dist[x] + z。

这种树结构称为图的一颗最短路径生成树。

所以结合Dijkstra和Prim算法，

  1. 从未被使用过的点中，取dist值最小的点p

  2. 点p与所有已被使用过的点x判断是否有d[p] == d[x] + edge(x, p)，有则++cnt

    该操作是计算点p有多少条最短路径边

  3. 用cnt更新答案后，点p标记为已被使用