题解 P7733 【抢救实验数据】

· · 题解

出题人的官方题解

看到这道题可能会有一些错误的想法，典型的就是来回都走最短路，但实际上到一个点去时走最短路，回来则不一定。如下图：

1 号点是起点，8 号点是毒气点，可以到达的点为 1~6。

首先 BFS 求出每个点到起点和泄露点的距离。简单的想法是暴力枚举每一个点 BFS 看能否回到起点，复杂度 O(n^2)，可以拿到 30 分。

我们令 t_x 表示能够回到起点到达 x 点的最晚时间，那么起点相邻的点都是它们到毒气点的距离。对于其他的点 u 有 t_u=\max\limits_{(u,v) \in E}(t_v)-1。
把所有起点相邻的点放进一个堆，用一个优先队列 BFS，每个点 x 第一次被更新的时候就得到了 t_x，复杂度 O(n \log n)，可以获得 70 分。
然后你会发现 t_x \leq n，并且堆中 t 的最大值单调不增，所以可以用一个 std::vector 来代替这个堆，复杂度 O(n+m)，可以通过此题。

#include <algorithm>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
struct Edge {
  int to, nxt;
} e[10000001];
int n, m, E, head[5000001], s, t, dis[5000001], h[5000001];
std::vector<int> q2[5000001];
bool vis[5000001];
class Queue {
 public:
  Queue() { head_ = tail_ = 0; }
  bool Empty() { return head_ == tail_; }
  void Clear() { head_ = tail_ = 0; }
  void Push(int x) { a_[tail_++] = x; }
  int Front() { return a_[head_]; }
  void Pop() { head_++; }
  ~Queue() {}

 private:
  int head_, tail_, a_[5000001];
} q;
char gc() {
  static char now[1 << 20], *S, *T;
  if (T == S) {
    T = (S = now) + std::fread(now, 1, 1 << 20, stdin);
    if (T == S) return EOF;
  }
  return *S++;
}
template <typename T>
void Read(T &x) {
  x = 0;
  char c = gc();
  while (c < '0' || c > '9') c = gc();
  x = c - '0';
  while ((c = gc()) >= '0' && c <= '9') x = x * 10 + c - '0';
}
template <typename T, typename... Args>
void Read(T &x, Args &... args) {
  Read(x);
  Read(args...);
}
void checkmax(int &x, int y) {
  if (x < y) x = y;
}
void checkmin(int &x, int y) {
  if (x > y) x = y;
}
void Add(int f, int t) {
  e[E].to = t;
  e[E].nxt = head[f];
  head[f] = E++;
}
int main(int argc, char const *argv[]) {
  std::memset(head, -1, sizeof(head));
  Read(n, m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    Read(u, v);
    Add(u, v);
    Add(v, u);
  }
  Read(s, t);
  std::memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  q.Push(s);
  vis[s] = true;
  while (!q.Empty()) {
    int u = q.Front();
    q.Pop();
    for (int i = head[u]; i != -1; i = e[i].nxt) {
      int v = e[i].to;
      if (vis[v]) continue;
      dis[v] = dis[u] + 1;
      q.Push(v);
      vis[v] = true;
    }
  }
  std::memset(h, 0x3f, sizeof(h));
  std::memset(vis, false, sizeof(vis));
  q.Clear();
  q.Push(t);
  h[t] = 0;
  vis[t] = true;
  while (!q.Empty()) {
    int u = q.Front();
    q.Pop();
    for (int i = head[u]; i != -1; i = e[i].nxt) {
      int v = e[i].to;
      if (vis[v] || v == s) continue;
      h[v] = h[u] + 1;
      q.Push(v);
      vis[v] = true;
    }
  }
  std::memset(vis, false, sizeof(vis));
  vis[s] = true;
  int max = 0;
  for (int i = head[s]; i != -1; i = e[i].nxt) {
    int v = e[i].to;
    if (h[v] > 5000000) continue;
    q2[h[v]].emplace_back(v);
    checkmax(max, h[v]);
    vis[v] = true;
  }
  for (int i = max; i >= 1; i--)
    for (auto &&u : q2[i])
      for (int j = head[u]; j != -1; j = e[j].nxt) {
        int v = e[j].to;
        if (vis[v]) continue;
        checkmin(h[v], h[u] - 1);
        vis[v] = true;
        q2[h[v]].emplace_back(v);
      }
  int ans = 0;
  for (int i = 1; i <= n; i++)
    ans += (vis[i] || h[i] == 0x3f3f3f3f) && (dis[i] < h[i]);
  std::cout << ans - 1;
  return 0;
}