专栏文章

[COTS 2014] 城市建设 / GRAD

MMrPython小河狸贝瓦
P11757题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min8rj33
此快照首次捕获于
2025/12/01 22:25
3 个月前
此快照最后确认于
2025/12/01 22:25
3 个月前
查看原文
LCA 原句：直接建三角形的树。我由这句话推出了与他很不一样的做法。
一句话题解：将三角形视为节点建图，图可以是一棵树，树上倍增。
本题解矩阵右乘。
本题的修改操作，每次相当于在图中添加一个三角形，且这个三角形与已有的某个三角形相连。从一个点到另一个点，相当于在三角形的边上不断移动，且每次都是从一个三角形切换到另一个三角形（由三角形不等式可得，在某个三角形上走两条边一定不优）。
既然如此，考虑图论建模，将三角形抽象成图上的点，两个三角形共用一条边时在图中将二者连接起来。每个三角形都记录一下他对应的三个城市是什么。三角形 A 到 B 的边权就是 3×33 \times 3 的 矩阵，内容为 A 中某一点到 B 中某一点的最短路。由于两个三角形相邻，还有三角形不等式加持，随便求。
倘若我们知道了某城市到某三角形所对应三个城市的最短路程，再通过一条边就可以转移到下一个三角形。方法为：将三个距离记成一个 1×31 \times 3 的矩阵，通过 (min⁡,+)(\min, +) 矩阵乘法乘上该边边权。由于三角形不等式，不可能绕一大圈再过去。
在图上找路径不大可做，但我们发现其实可在树上做即可。如图： pic1 三个三角形共用一条边，根本不需要连 33 条边，22 条就够了。假如在图上连接了 △A\triangle A 和 △B\triangle B、△B\triangle B 和 △C\triangle C，一条从城市 X△AX_{\triangle A} 到 Y△CY_{\triangle C} 的路径可以被视为 X△A→P△A→P△B→P△C→Y△CX_{\triangle A} \rightarrow P_{\triangle A} \rightarrow P_{\triangle B} \rightarrow P_{\triangle C} \rightarrow Y_{\triangle C}。同一个点之间的距离为 00，因此这样建图仍然可以得到正确答案。
转换成树就简单了。可以用倍增维护树上两点之间的路径矩阵之积。写起来有点屎。
CPP
#include <mrpython/utility.hpp>
#include <bits/stdc++.h>
using namespace std;
istream& fin = cin;
ostream& fout = cout;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
template <typename T, size_t N, size_t M> struct matrix {
  T m[N][M];
  template <typename F = std::plus<>>
  friend matrix plus(matrix x, matrix const& y, F const& f = {}) {
    for (size_t i = 0; i < N; ++i)
      for (size_t j = 0; j < M; ++j)
        x.m[i][j] = f(x.m[i][j], y.m[i][j]);
    return x;
  }
  constexpr matrix& operator+=(matrix const& y) {
    return plus(y);
  }
  constexpr friend matrix operator+(matrix x, matrix const& y) {
    return x += y;
  }
  template <size_t L, typename F = std::plus<>, typename G = std::multiplies<>>
  constexpr static matrix<T, N, L> multiplies(matrix<T, N, M> const& a,
                                              matrix<T, M, L> const& b,
                                              F const& f = {}, G const& g = {},
                                              T const& init = 0) {
    matrix<T, N, L> ans{};
    for (size_t i = 0; i < N; ++i)
      for (size_t j = 0; j < L; ++j) {
        ans.m[i][j] = init;
        for (size_t k = 0; k < M; ++k)
          ans.m[i][j] = f(ans.m[i][j], g(a.m[i][k], b.m[k][j]));
      }
    return ans;
  }

  template <size_t L>
  constexpr friend matrix<T, N, L> operator*(matrix<T, N, M> const& a,
                                             matrix<T, M, L> const& b) {
    return matrix<T, N, M>::multiplies<L>(a, b);
  }
  constexpr matrix& operator*=(matrix<T, M, M> const& x) {
    return *this = *this * x;
  }
};
using Mt = matrix<double, 3, 3>;
constexpr ui W = 20;
auto main(void) -> int {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  vector<complex<double>> ps;
  {
    ui x, y, z, w;
    fin >> x >> y >> z >> w;
    ps = {
        {{(double)x, (double)y}, {(double)z, (double)w}}
    };
  }
  vector<size_t> tids = {0, 0};
  map<pair<size_t, size_t>, size_t> edges = {
      {{0, 1}, 0}
  };
  vector<array<size_t, 3>> tps;
  vector<size_t> deepth = {0};
  vector<array<pair<size_t, Mt>, W>> jmp = {{}};
  auto mgMt = []<typename T, size_t N, size_t M, size_t L>(
                  matrix<T, N, M> const& a, matrix<T, M, L> const& b) {
    return matrix<T, N, M>::multiplies(a, b, mrpython::min(), plus(),
                                       numeric_limits<double>::infinity());
  };
  size_t q;
  fin >> q;
  fout << fixed << setprecision(6);
  while (q--) {
    char op;
    fin >> op;
    if (op == 'd') {
      complex<double> pv;
      {
        ui x, y;
        fin >> x >> y;
        pv = {(double)x, (double)y};
      }
      size_t px, py;
      fin >> px >> py;
      --px, --py;
      if (px > py)
        swap(px, py);
      size_t pid = ps.size();
      size_t tid = tps.size();
      size_t fa = edges.at({px, py});
      ps.emplace_back(pv);
      tids.emplace_back(tid);
      edges.insert({
          {px, pid},
          tid
      });
      edges.insert({
          {py, pid},
          tid
      });
      tps.push_back({px, py, pid});
      if (tid != 0)
        deepth.emplace_back(deepth[fa] + 1);
      Mt mt;
      for (size_t i = 0; i < 3; ++i)
        for (size_t j = 0; j < 3; ++j) {
          size_t pi = tps[tid][i], pj = tps[fa][j];
          if (((tps[tid][i] == pid && tps[fa][j] != px && tps[fa][j] != py) ||
               (tps[tid][j] == pid && tps[fa][i] != px && tps[fa][i] != py)) &&
              !edges.contains({min(pi, pj), max(pi, pj)})) {
            mt.m[i][j] = min(abs(ps[pi] - ps[px]) + abs(ps[px] - ps[pj]),
                             abs(ps[pi] - ps[py]) + abs(ps[py] - ps[pj]));
          } else
            mt.m[i][j] = abs(ps[pi] - ps[pj]);
        }
      if (tid != 0)
        jmp.push_back({{{fa, mt}}});
      for (size_t t = 1; t < W; ++t) {
        size_t tm = jmp[tid][t - 1].first;
        jmp[tid][t] = {jmp[tm][t - 1].first,
                       mgMt(jmp[tid][t - 1].second, jmp[tm][t - 1].second)};
      }
    } else if (op == 'u') {
      size_t px, py;
      fin >> px >> py;
      --px, --py;
      size_t tx = tids[px], ty = tids[py];
      if (deepth[tx] < deepth[ty])
        swap(px, py), swap(tx, ty);
      matrix<double, 1, 3> mx, my;
      for (size_t i = 0; i < 3; ++i) {
        mx.m[0][i] = abs(ps[tps[tx][i]] - ps[px]);
        my.m[0][i] = abs(ps[tps[ty][i]] - ps[py]);
      }
      for (ui t = W - 1; t < W; --t)
        if (((deepth[tx] - deepth[ty]) >> t) & 1u) {
          mx = mgMt(mx, jmp[tx][t].second);
          tx = jmp[tx][t].first;
        }
      assert(deepth[tx] == deepth[ty]);
      if (tx != ty) {
        for (ui t = W - 1; t < W; --t)
          if (jmp[tx][t].first != jmp[ty][t].first) {
            mx = mgMt(mx, jmp[tx][t].second);
            tx = jmp[tx][t].first;
            my = mgMt(my, jmp[ty][t].second);
            ty = jmp[ty][t].first;
          }
        mx = mgMt(mx, jmp[tx][0].second);
        tx = jmp[tx][0].first;
        my = mgMt(my, jmp[ty][0].second);
        ty = jmp[ty][0].first;
      }
      assert(tx == ty);
      double ans = numeric_limits<double>::infinity();
      for (size_t i = 0; i < 3; ++i)
        ans = min(ans, mx.m[0][i] + my.m[0][i]);
      fout << ans << '\n';
    }
  }
  return 0;
}

评论

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

正在加载评论...