526互联

[题解] CF632F - Swimmers in the Pool

发布时间 2023-10-03 20:48:15作者: フランドール·スカーレット

CF632F - Swimmers in the Pool

题目传送门

题意

给定一个大小为 \(n \times n\) 的矩阵 \(A\) 。假设 \(A\) 满足以下条件，那么称该矩阵为 MAGIC ，否则为 NOT MAGIC ，并输出对应的属性（即 \(A\) 是 MAGIC 还是 NOT MAGIC)。

  1. $ A_{i, j} = A_{j, i}$ ；
  2. $ A_{i,i} = 0 $ ；
  3. $ 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";
}