Monge checker
(other_algorithms/monge_checker.hpp)

• View this file on GitHub
• Last update: 2025-07-23 23:05:34+09:00
• Include: #include "other_algorithms/monge_checker.hpp"
• Link: https://hackmd.io/@tatyam-prime/monge1

与えられた一般の $n \times m$ 行列や $n$ 頂点 DAG の重み行列の Monge 性および Anti-Monge 性を確認し，以下の結果を出力する．

• Monge であった場合， Monge OK と出力
• Monge ではないが anti-Monge であった場合， Not Monge, but Anti-Monge OK と出力
• Monge でも anti-Monge でもない場合， Not Monge! と出力し，続けて Monge 性に反する $2 \times 2$ 小行列を出力

計算量は $O(nm)$ や $O(n^2)$ なので，ジャッジへの提出にこの関数の実行を含めると TLE となりうるので注意．

使用方法

行列を std::vector<std::vector<long long>> 等の形で直接与えるのではなく， int 2 つを引数として重みを返す関数 cost(int, int) を引数として与えればよい．

$n$ 頂点 DAG の辺重み関数の Monge 性判定

int n;  // 頂点: 0, 1, ..., (n - 1)
using T = long long;
T INF;
auto cost = [&](int i, int j) -> T {
    // Return weight of directed edge i->j, or INF if the edge does not exist.
};

cerr << check_dag_monge(cost, INF, n) << endl;

Monge 性の確認方法

隣接する 2 行と 2 列の要素からなる全ての $2 \times 2$ 小行列に対する Monge 性を確認すればよい [1]．

Links

• [1] [Monge まとめ①] Monge 性とは？ - HackMD

Code

#pragma once

#include <sstream>
#include <string>

// Check whether cost(i, j) is Monge or not
// Complexity: O(nm)
// https://hackmd.io/@tatyam-prime/monge1
template <bool only_upper = false>
std::string check_matrix_monge(auto cost, auto inf, int n, int m) {
    if (m < 0) m = n;

    auto Detect = [n, m, inf](auto f) -> std::tuple<bool, int, int> {
        for (int i = 0; i + 1 < n; ++i) {
            for (int j = only_upper ? (i + 2) : 0; j + 1 < m; ++j) {
                const auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j),
                           f11 = f(i + 1, j + 1);
                if (f00 >= inf or f01 >= inf) continue;
                if (f00 + f11 > f10 + f01) { return {false, i, j}; }
            }
        }
        return {true, -1, -1};
    };

    if (auto [is_monge, i, j] = Detect(cost); is_monge) {
        return "Monge OK";
    } else if (auto [is_anti_monge, ai, aj] = Detect([&cost, inf](int i, int j) {
                   auto ret = cost(i, j);
                   return ret == inf ? inf : -ret;
               });
               is_anti_monge) {
        return "Not Monge, but Anti-Monge OK";
    } else {
        std::stringstream ret;
        ret << "Not Monge!\n";
        ret << "    j=" << std::to_string(j) << "   j=" << std::to_string(j + 1) << "\n";
        ret << "i=" << std::to_string(i) << " " << cost(i, j) << " " << cost(i, j + 1) << "\n";
        ret << "i=" << std::to_string(i + 1) << " " << cost(i + 1, j) << " " << cost(i + 1, j + 1);
        return ret.str();
    }
}

// Check whether graph weight is Monge or not
// Complexity: O(n^2)
std::string check_dag_monge(auto cost, auto inf, int n) {
    return check_matrix_monge<true>(cost, inf, n, n);
}

#line 2 "other_algorithms/monge_checker.hpp"

#include <sstream>
#include <string>

// Check whether cost(i, j) is Monge or not
// Complexity: O(nm)
// https://hackmd.io/@tatyam-prime/monge1
template <bool only_upper = false>
std::string check_matrix_monge(auto cost, auto inf, int n, int m) {
    if (m < 0) m = n;

    auto Detect = [n, m, inf](auto f) -> std::tuple<bool, int, int> {
        for (int i = 0; i + 1 < n; ++i) {
            for (int j = only_upper ? (i + 2) : 0; j + 1 < m; ++j) {
                const auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j),
                           f11 = f(i + 1, j + 1);
                if (f00 >= inf or f01 >= inf) continue;
                if (f00 + f11 > f10 + f01) { return {false, i, j}; }
            }
        }
        return {true, -1, -1};
    };

    if (auto [is_monge, i, j] = Detect(cost); is_monge) {
        return "Monge OK";
    } else if (auto [is_anti_monge, ai, aj] = Detect([&cost, inf](int i, int j) {
                   auto ret = cost(i, j);
                   return ret == inf ? inf : -ret;
               });
               is_anti_monge) {
        return "Not Monge, but Anti-Monge OK";
    } else {
        std::stringstream ret;
        ret << "Not Monge!\n";
        ret << "    j=" << std::to_string(j) << "   j=" << std::to_string(j + 1) << "\n";
        ret << "i=" << std::to_string(i) << " " << cost(i, j) << " " << cost(i, j + 1) << "\n";
        ret << "i=" << std::to_string(i + 1) << " " << cost(i + 1, j) << " " << cost(i + 1, j + 1);
        return ret.str();
    }
}

// Check whether graph weight is Monge or not
// Complexity: O(n^2)
std::string check_dag_monge(auto cost, auto inf, int n) {
    return check_matrix_monge<true>(cost, inf, n, n);
}

Back to top page