专栏文章

题解：P11757 [COTS 2014] 城市建设 / GRAD

wweilycoder东临碣石
P11757题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min8nrmw
此快照首次捕获于
2025/12/01 22:22
3 个月前
此快照最后确认于
2025/12/01 22:22
3 个月前
查看原文
这题属于那种真的一句话就能讲完，但是想破头也做不出来的题。
试试 CF 风格题解。
Hint1：每次加进来一个点后，会对原有的点产生什么影响？
发现其实没啥影响。
每次加一个点 PP 的方式是选择两个已经连边的点 A,BA,B，添加无向边 PA,PBPA,PB。
根据平面上三角性的几何性质，AB⩽PA+PBAB\leqslant PA+PB，因此不会原有的点之间的最短路产生任何影响。
由此可以打出 O(n2)O\left(n^2\right) 暴力。
同时注意到修改和查询的独立性都很高，可以再一定程度上离线。
Hint2：把图画到平面上，每次新加一个点，图形态的变化是怎样的？最终图的形态是怎样的？有什么启发？
这个真难想吧，我至今没能从中平滑插入一个思考过程。
发现实际上每次加点都引入了一个三角形 ABPABP，并且这个三角形通过边 ABAB 与其他三角形相连。
Solution
可以发现能够把每个三角形看作图中一个节点，三角形间的公共边看作图中的一条边。这样容易把原图转换为一棵树。
为了维护最短路信息，可以在边 u→vu\to v 上维护一个 3×33\times 3 的矩阵 FF，Fi,jF_{i,j} 表示从三角形 uu 的第 ii 个点到三角形 vv 的第 jj 个点的最短路。
需要注意这里的边和矩阵显然都需要是有方向的，对于反边 v→uv\to u，边权应该是原边边权的转置 FTF^\mathrm{T}。
分析一下可以发现，对于一条路径，其权值应为路径上所有边边权的 (min⁡,+)\left(\min,+\right) 广义矩阵乘法。
树上倍增维护即可。
另外加点的时候可能发现公共边 ABAB 可能被多个三角形公用，可以选择任意一个与新三角形连边。
CodeCPP
#include <bits/stdc++.h>
using namespace std;

using Point = complex<double>;

static constexpr size_t null = numeric_limits<size_t>::max();
static constexpr double INF = numeric_limits<double>::infinity();

template <size_t N> struct Matrix {
  double M[N][N];

  Matrix() {
    for (size_t i = 0; i < N; ++i)
      for (size_t j = 0; j < N; ++j)
        M[i][j] = (i == j ? 0.0 : INF);
  }

  double &operator()(size_t i, size_t j) { return M[i][j]; }
  const double &operator()(size_t i, size_t j) const { return M[i][j]; }

  void close() {
    for (size_t k = 0; k < N; ++k)
      for (size_t i = 0; i < N; ++i)
        for (size_t j = 0; j < N; ++j)
          M[i][j] = min(M[i][j], M[i][k] + M[k][j]);
  }

  Matrix friend operator*(const Matrix &A, const Matrix &B) {
    Matrix C;
    for (size_t i = 0; i < N; ++i)
      C(i, i) = INF;
    for (size_t i = 0; i < N; ++i)
      for (size_t k = 0; k < N; ++k)
        for (size_t j = 0; j < N; ++j)
          C(i, j) = min(C(i, j), A(i, k) + B(k, j));
    return C;
  }

  Matrix transpose() const {
    Matrix B;
    for (size_t i = 0; i < N; ++i)
      for (size_t j = 0; j < N; ++j)
        B(j, i) = M[i][j];
    return B;
  }
};

using Matrix3 = Matrix<3>;
using Matrix6 = Matrix<6>;

struct Tree {
  vector<size_t> depth;
  vector<vector<size_t>> parent;
  vector<vector<Matrix3>> weight;

  Tree() = default;

  void ensure_size(size_t n) {
    if (n <= depth.size())
      return;
    depth.resize(n, 0);
    for (size_t i = 0; i < parent.size(); ++i) {
      parent[i].resize(n, null);
      weight[i].resize(n, Matrix3());
    }
    while ((1u << parent.size()) <= n) {
      parent.emplace_back(n, null);
      weight.emplace_back(n, Matrix3());
    }
  }

  size_t get_depth(size_t u) const { return u == null ? 0 : depth[u]; }

  void add_node(size_t u, size_t p, const Matrix3 &w) {
    ensure_size(u + 1);
    depth[u] = get_depth(p) + 1;
    parent[0][u] = p;
    weight[0][u] = w;
    for (size_t k = 1; k < parent.size(); ++k) {
      size_t mid = parent[k - 1][u];
      if (mid == null)
        break;
      parent[k][u] = parent[k - 1][mid];
      weight[k][u] = weight[k - 1][u] * weight[k - 1][mid];
    }
  }

  Matrix3 query(size_t u, size_t v) const {
    bool swapped = false;
    Matrix3 res_u, res_v;
    if (get_depth(u) < get_depth(v))
      swap(u, v), swapped = true;
    for (size_t k = parent.size(); k-- > 0;)
      if (get_depth(u) - get_depth(v) >= (1u << k)) {
        res_u = res_u * weight[k][u];
        u = parent[k][u];
      }
    if (swapped)
      swap(u, v), swap(res_u, res_v);
    if (u == v)
      return res_u * res_v.transpose();
    for (size_t k = parent.size(); k-- > 0;)
      if (parent[k][u] != parent[k][v]) {
        res_u = res_u * weight[k][u];
        res_v = res_v * weight[k][v];
        u = parent[k][u], v = parent[k][v];
      }
    res_u = res_u * weight[0][u];
    res_v = res_v * weight[0][v];
    return res_u * res_v.transpose();
  }
};

struct City {
  vector<Point> city;
  map<pair<size_t, size_t>, double> roads;

  Tree tree;

  vector<size_t> node_to_triangle;
  map<pair<size_t, size_t>, size_t> edge_to_triangle;
  vector<tuple<size_t, size_t, size_t>> triangle;

  City() = default;

  double get_edge(size_t u, size_t v) {
    if (u == v)
      return 0.0;
    auto it = roads.find({u, v});
    return it == roads.end() ? INF : it->second;
  }

  size_t add_point(const Point &p) {
    city.push_back(p);
    node_to_triangle.push_back(null);
    return city.size() - 1;
  }

  void add_edge(size_t u, size_t v) {
    roads[{u, v}] = abs(city[v] - city[u]);
    roads[{v, u}] = abs(city[v] - city[u]);
  }

  void add_edge(const Point &a, const Point &b) {
    size_t u = add_point(a), v = add_point(b);
    add_edge(u, v);
  }

  void add_city(const Point &p, size_t a, size_t b) {
    auto it = edge_to_triangle.find({a, b});

    size_t c = add_point(p);
    add_edge(c, a), add_edge(c, b);

    size_t t = triangle.size();
    triangle.emplace_back(a, b, c);

    if (it != edge_to_triangle.end()) {
      const auto &[x, y, z] = triangle[it->second];
      array<size_t, 6> nodes{a, b, c, x, y, z};
      Matrix6 W;
      for (size_t i = 0; i < 6; ++i)
        for (size_t j = 0; j < 6; ++j)
          W(i, j) = get_edge(nodes[i], nodes[j]);
      W.close();
      Matrix3 F;
      for (size_t i = 0; i < 3; ++i)
        for (size_t j = 0; j < 3; ++j)
          F(i, j) = W(i, j + 3);
      tree.add_node(t, it->second, F);
    }

    node_to_triangle[a] = t;
    node_to_triangle[b] = t;
    node_to_triangle[c] = t;
    edge_to_triangle[{a, b}] = t;
    edge_to_triangle[{b, a}] = t;
    edge_to_triangle[{b, c}] = t;
    edge_to_triangle[{c, b}] = t;
    edge_to_triangle[{a, c}] = t;
    edge_to_triangle[{c, a}] = t;
  }

  double query(size_t u, size_t v) {
    double direct = get_edge(u, v);
    if (direct < INF)
      return direct;
    size_t tu = node_to_triangle[u], tv = node_to_triangle[v];
    Matrix3 M = tree.query(tu, tv);
    auto get_idx = [&](size_t node, const tuple<size_t, size_t, size_t> &triangle) {
      if (node == get<0>(triangle))
        return 0;
      else if (node == get<1>(triangle))
        return 1;
      else
        return 2;
    };
    size_t iu = get_idx(u, triangle[tu]);
    size_t iv = get_idx(v, triangle[tv]);
    return M(iu, iv);
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin.exceptions(cin.failbit | cin.badbit);
  City city;
  double x0, y0, x1, y1;
  cin >> x0 >> y0 >> x1 >> y1;
  city.add_edge(Point(x0, y0), Point(x1, y1));
  size_t n;
  cin >> n;
  while (n--) {
    string op;
    cin >> op;
    if (op == "d") {
      double x, y;
      size_t a, b;
      cin >> x >> y >> a >> b;
      city.add_city(Point(x, y), a - 1, b - 1);
    } else {
      size_t a, b;
      cin >> a >> b;
      double ans = city.query(a - 1, b - 1);
      cout << fixed << setprecision(6) << ans << '\n';
    }
  }
  return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...