acwing-342. 道路与航线

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • flood-fill找连通块
  • 拓扑排序
  • 最短路

题解

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4 + 50, maxm = 1e5 + 50;
int n, m, p, st, tot = -1, head[maxn], d[maxn];
// block：每个点所在的连通块，cnt：一共多少连通块，ind：每个连通块的入度
int block[maxn], cnt, ind[maxn];
// arr[k]：第k个连通块有哪些元素
vector<int> arr[maxn];
// 拓扑排序的队列
queue<int> q1;

struct node {
  // flag为0代表是道路，1代表是航线
  int v_, w_, nxt_, flag_;
} g[maxm << 1];

void add(int u, int v, int w, int flag) {
  g[++tot].v_ = v, g[tot].w_ = w, g[tot].flag_ = flag, g[tot].nxt_ = head[u],
  head[u] = tot;
}

void dfs(int u, int k) {
  block[u] = k, arr[k].push_back(u);
  for (int i = head[u]; ~i; i = g[i].nxt_) {
    int v = g[i].v_, w = g[i].w_, flag = g[i].flag_;
    if (block[v] || flag) continue;
    dfs(v, k);
  }
}

void init() {
  int u, v, w;
  memset(head, -1, sizeof(head)), memset(d, 0x3f, sizeof(d));
  for (int i = 1; i <= m; ++i) {
    cin >> u >> v >> w;
    add(u, v, w, 0), add(v, u, w, 0);
  }
  for (int i = 1; i <= p; ++i) {
    cin >> u >> v >> w;
    add(u, v, w, 1);
  }
}

void dijkstra(int k) {
  priority_queue<pair<int, int>> q2;
  bool vis[maxn];
  memset(vis, 0, sizeof(vis));
  for (auto u : arr[k]) {
    q2.push({-d[u], u});
  }
  while (!q2.empty()) {
    int u = q2.top().second;
    q2.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; ~i; i = g[i].nxt_) {
      int v = g[i].v_, w = g[i].w_, flag = g[i].flag_;
      // 处理航线
      if (flag) {
        d[v] = min(d[v], d[u] + w);
        if (--ind[block[v]] == 0) q1.push(block[v]);
      } else {
        if (d[v] > d[u] + w) {
          d[v] = d[u] + w;
          q2.push({-d[v], v});
        }
      }
    }
  }
}

void toposort() {
  // 遍历所有航线，统计所有连通块的入度
  for (int i = 1; i <= cnt; ++i) {
    for (auto u : arr[i]) {
      for (int j = head[u]; ~j; j = g[j].nxt_) {
        int v = g[j].v_, flag = g[j].flag_;
        if (flag) ++ind[block[v]];
      }
    }
  }
  // 入度为0的塞进队列
  for (int i = 1; i <= cnt; ++i) {
    if (!ind[i]) q1.push(i);
  }
  // 起点最短路初始化
  d[st] = 0;
  // 拓扑排序
  while (!q1.empty()) {
    int k = q1.front();
    q1.pop();
    dijkstra(k);
  }
}

int main() {
  cin >> n >> m >> p >> st;
  init();
  // 求连通块
  for (int i = 1; i <= n; ++i) {
    if (!block[i]) {
      dfs(i, ++cnt);
    }
  }
  // 对连通块进行拓扑排序
  toposort();
  for (int i = 1; i <= n; ++i) {
    // 因为有负边，0x3f3f3f3f - x显然小于0x3f3f3f3f，会被错误更新
    // 两种办法，第一种如果起点就是0x3f3f3f3f就不要往下更新，但会增加部分码量
    // 第二种设置一个路径理想最大值，比如结点数 * 最大边权，推荐这种方式
    if (d[i] > n * 10000)
      cout << "NO PATH" << endl;
    else
      cout << d[i] << endl;
  }
  return 0;
}

思路

SPFA的时间复杂度是\(O\left( nm \right)\)，直接用显然会超时。

根据题意，道路双向边均非负，航线单向边可能为负数，且航线单向边不构成环。

双向边会形成若干个连通块，而单向边则负责连接不同连通块，整个图就变成了DAG有向无环图。

使用拓扑排序的框架顺序处理每个连通块，而每个连通块的内部使用Dijkstra求最短路即可。

详细的算法流程如下：

  1. 用dfs的flood-fill操作划分连通块，block[x]代表每个点x所处的连通块，vector<int> arr[k]存储第k个连通块有哪些点。

  2. 遍历所有航线，统计每个连通块的总入度，ind[x]代表连通块x的入度数

  3. 建立拓扑排序队列q1，如果连通块入度为0就插入队列

  4. 取出队头的连通块k，执行Dijkstra算法：

    1. 建立一个堆，把arr[k]所有元素塞入，即连通块k的所有节点

    2. 从堆上取出d[u]最小的节点u

    3. 若u被扩展过，回到步骤2，否则下一步

    4. 扫描从u出发的所有边(v, w, flag)，用d[u] + w更新d[v]

    5. 如果flag == 0，说明该条边不是航线，还在连通块内；若d[v]被更新，则把v塞入堆

    6. 如果flag == 1，说明该条边是航线，令ind[block[v]]减去1，

      若入度减为0，把连通块block[v]塞入q1的队列末尾

    7. 重复2-6操作，直到堆为空

输出时，不能简单地判断d[x] == 0x3f3f3f3f，举个例子：

a点和b点都是0x3f3f3f3f，两者组成连通块，边权为负数，且该连通块不与其它连通块相通。

然而因为有负边，0x3f3f3f3f - x显然小于0x3f3f3f3f，d[b]会被错误更新。

两种办法，第一种如果起点就是0x3f3f3f3f就不要往下更新，但会增加部分码量和提高错误率；

第二种设置一个路径理想最大值，比如结点数 * 最大边权，推荐这种方式！