src/graph/mst/manhattan/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | //! USE Kruskal too get MST | ||
| 8 | // @return edges MAYBE in MST, {d(u, v), u, v} | ||
| 9 | template <class T> | ||
| 10 | requires std::is_signed_v<T> | ||
| 11 | 16 | vec<edge_t<T>> manhattan_mst(vecpt<T> vp) NE { | |
| 12 | 16 | vecu id(vp.size()); | |
| 13 | 16 | std::iota(begin(id), end(id), 0); | |
| 14 | 16 | vec<edge_t<T>> ret; | |
| 15 |
2/2✓ Branch 0 taken 64 times.
✓ Branch 1 taken 16 times.
|
80 | flt_ (u32, k, 0, 4) { |
| 16 | 367332970 | sort(id, {}, [&](u32 i) NE { return vp[i].first + vp[i].second; }); | |
| 17 |
2/2✓ Branch 5 taken 8518948 times.
✓ Branch 6 taken 64 times.
|
8519012 | for (map<T, u32> mp; auto i : id) { |
| 18 |
2/2✓ Branch 5 taken 15809260 times.
✓ Branch 6 taken 611469 times.
|
16420729 | for (auto it = mp.lower_bound(-vp[i].second); it != end(mp); mp.erase(it++)) { |
| 19 | 15809260 | u32 j = it->second; | |
| 20 |
2/2✓ Branch 4 taken 7907479 times.
✓ Branch 5 taken 7901781 times.
|
15809260 | if (T x_ = vp[i].first - vp[j].first, y_ = vp[i].second - vp[j].second; y_ > x_) break; |
| 21 | 7901781 | else ret.emplace_back(x_ + y_, i, j); | |
| 22 | } | ||
| 23 | 8518948 | mp[-vp[i].second] = i; | |
| 24 | } | ||
| 25 |
2/2✓ Branch 7 taken 8518948 times.
✓ Branch 8 taken 64 times.
|
8519012 | for (auto& [x, y] : vp) |
| 26 |
2/2✓ Branch 0 taken 4259474 times.
✓ Branch 1 taken 4259474 times.
|
8518948 | if (k & 1) x *= -1; |
| 27 | 4259474 | else swap(x, y); | |
| 28 | } | ||
| 29 | 16 | return ret; | |
| 30 | 16 | } | |
| 31 | |||
| 32 | } // namespace tifa_libs | ||
| 33 |