CF632F - Swimmers in the Pool
题意
给定一个大小为 \(n \times n\) 的矩阵 \(A\) 。假设 \(A\) 满足以下条件，那么称该矩阵为 MAGIC ，否则为 NOT MAGIC ，并输出对应的属性（即 \(A\) 是 MAGIC 还是 NOT MAGIC)。
- $ A_{i, j} = A_{j, i}$ ；
- $ A_{i,i} = 0 $ ；
- $ A_{i,j} \le \max { A_{i,k}, A_{j,k} } $。
思路
对于条件 \(1\) 和 \(2\) ，我们可以在 \(O(n^2)\) 的时间复杂度下直接进行判断即可。
对于条件 \(3\) ，我们在进行判断时需要对矩阵进行一下转换。
由条件 \(1\) ，我们可以知道这个矩阵是一个对称矩阵，那么我们可以想到图的一种表示方式：邻接矩阵。那么，在这里我们可以发现，整个矩阵描述的对象，是一个无向图。
由条件 \(2\) ，我们可以知道，该图没有自环（或者说自环的边权为 \(0\) ，可以忽略)。
因此，我们可以发现，我们是要在一张无向图上，判断 \((i, j)\) 这条边的边权是否小于等于 \((i, k)\) 和 \((k, j)\) 的边权。我们可以依据这个规律，不断扩展这个不等式：
\[A_{i, j} \le \max \{ A_{i, k}, A_{j, k} \} \\ A_{i, k} \le \max \{ A_{i, t}, A_{t, k} \} \\ \cdots \]可以发现，如果我们不断扩展，那么该子问题可以转化为：问对于 \((i, j)\) 这条边，是否存在 \(i\) 到 \(j\) 的所有可能简单路径中，所有路径上边的边权都是大于等于 \((i, j)\) 的。
那么这样一来就很好解决了，我们要知道 \(i\) 到 \(j\) 所有路径上的情况，那么我们直接建一颗最小生成树就可以了，最小生成树上的路径边，即为原图中所有可能路径边的最小情况。
剩下的，我们只需要利用最小生成树，对所有 \(A_{i, j}\) 进行查询即可。查询的内容为：\(i\) 到 \(j\) 在最小生成树上的路径的边，其最最大的边是否大于等于 \(a_{i, j}\) 。
这个问题我们可以对最小生成树进行树剖+RMQ 查询，也可以使用 Kruskal 重构树查询。
实现
class DisjointSet {
private:
std::vector<int> _leader;
std::size_t _setCount;
public:
explicit DisjointSet(std::size_t size)
: _leader(size, -1), _setCount(size) {}
private:
auto _InRange(int x) const noexcept -> bool {
return 0 <= x && x < (int)_leader.size();
}
auto _GetLeader(int x) -> int {
if (_leader[x] <= -1) {
return x;
}
return _leader[x] = _GetLeader(_leader[x]);
}
auto _GetCount(int x) -> int {
return -_leader[_GetLeader(x)];
}
template <std::strict_weak_order<int, int> _Compare>
auto _MergeIf(int a, int b, const _Compare &comp) -> bool {
a = _GetLeader(a);
b = _GetLeader(b);
if (!comp(a, b)) {
std::swap(a, b);
}
if (!comp(a, b)) {
return false;
}
_leader[a] += _leader[b];
_leader[b] = a;
--_setCount;
return true;
}
auto _MergeTo(int a, int b) noexcept -> bool {
a = _GetLeader(a);
b = _GetLeader(b);
if (a == b) {
return false;
}
_leader[b] += _leader[a];
_leader[a] = b;
--_setCount;
return true;
}
public:
auto GetLeader(int x) -> int {
assert(_InRange(x));
return _GetLeader(x);
}
auto GetCount() const noexcept -> std::size_t {
return _setCount;
}
auto GetCount(int x) -> int {
assert(_InRange(x));
return _GetCount(x);
}
template <std::strict_weak_order<int, int> _Compare>
auto MergeIf(int a, int b, const _Compare &comp) -> bool {
assert(_InRange(a));
assert(_InRange(b));
return _MergeIf(a, b, comp);
}
auto MergeTo(int a, int b) -> bool {
assert(_InRange(a));
assert(_InRange(b));
return _MergeTo(a, b);
}
auto IsSame(int a, int b) -> bool {
assert(_InRange(a));
assert(_InRange(b));
return _GetLeader(a) == _GetLeader(b);
}
auto IsSame(std::initializer_list<int> list) -> bool {
bool ret = true;
int v = *list.begin();
for (auto x : list) {
ret = IsSame(v, x);
if (!ret)
break;
}
return ret;
}
template <typename _Iter>
requires std::input_iterator<_Iter> &&
std::same_as<typename std::iterator_traits<_Iter>::value_type,
int>
auto IsSame(_Iter first, _Iter last) {
bool ret = true;
int v = *first;
for (auto it = first + 1; it != last && ret; ++it) {
ret = IsSame(v, *it);
}
return ret;
}
auto Assign(std::size_t size) -> void {
_leader.assign(size, -1);
_setCount = size;
}
};
auto Main() -> void {
int n;
cin >> n;
vector mat(n, vector<int>(n));
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < n; j += 1) {
cin >> mat[i][j];
}
}
for (int i = 0; i < n; i += 1) {
if (mat[i][i] != 0) {
cout << "NOT MAGIC\n";
return;
}
for (int j = i + 1; j < n; j += 1) {
if (mat[i][j] != mat[j][i]) {
cout << "NOT MAGIC\n";
return;
}
}
}
vector<tuple<int,int,int>> edge;
edge.reserve(n * (n / 2 + 1));
for (int i = 0; i < n; i += 1) {
for (int j = i + 1; j < n; j += 1) {
edge.emplace_back(mat[i][j], i, j);
}
}
ranges::sort(edge, std::less{}, [](auto &&x) { return std::get<0>(x); });
DisjointSet dsu(n * 2);
int tot = n;
vector<int> vw(n * 2);
vector adj(n * 2, vector<int>{});
for (auto [w, u, v] : edge) {
int fu = dsu.GetLeader(u), fv = dsu.GetLeader(v);
if (fu != fv) {
vw[tot] = w;
dsu.MergeTo(fu, tot);
dsu.MergeTo(fv, tot);
adj[tot].emplace_back(fu);
adj[tot].emplace_back(fv);
adj[fu].emplace_back(tot);
adj[fv].emplace_back(tot);
tot += 1;
}
}
vector<int> dep(n * 2, -1), siz(dep), top(dep), son(dep), fa(dep);
auto build = [&](int tree_root) -> void {
auto dfs1 = [&](auto &self, int from) -> void {
son[from] = -1;
siz[from] = 1;
for (auto to : adj[from]) {
if (dep[to] == -1) {
dep[to] = dep[from] + 1;
fa[to] = from;
self(self, to);
siz[from] += siz[to];
if (son[from] == -1 || siz[son[from]] < siz[to]) {
son[from] = to;
}
}
}
};
auto dfs2 = [&](auto &self, int from, int link_top) -> void {
top[from] = link_top;
if (son[from] == -1) {
return;
}
self(self, son[from], link_top);
for (auto to : adj[from]) {
if (to != son[from] && to != fa[from]) {
self(self, to, to);
}
}
};
dep[tree_root] = 0;
dfs1(dfs1, tree_root);
dfs2(dfs2, tree_root, tree_root);
};
build(tot - 1);
auto GetLca = [&](int a, int b) -> int {
while (top[a] != top[b]) {
if (dep[top[a]] < dep[top[b]]) {
swap(a, b);
}
a = fa[top[a]];
}
if (dep[a] > dep[b]) {
swap(a, b);
}
return a;
};
for (int i = 0; i < n; i += 1) {
for (int j = i + 1; j < n; j += 1) {
auto lca = GetLca(i, j);
if (mat[i][j] > vw[lca]) {
cout << "NOT MAGIC\n";
return;
}
}
}
cout << "MAGIC\n";
}