cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: AOJ2828 マトリョーシカ
(Test/AOJ/2828.test.cpp)

DAG上の最大重み付きパス被覆問題に帰着する。DAG上の最小パス被覆問題は最大二部マッチング問題に帰着するので、この問題は最小費用流で解けることが予想できる。

DAG上の最小パス被覆問題は以下のように解く

  1. $2\mid V\mid + 2$ 頂点用意する。 $V = \{ \text{source}, 0, 1, \dots, n - 1, 0’, 1’, \dots, (n - 1)’, \text{sink} \}$ とする。

  2. $\text{source}$ から頂点 $0, 1, \dots, n - 1$ に容量1の辺を張る

  3. 頂点 $0’, 1’, \dots, (n - 1)’$ から $\text{sink}$ に容量1の辺を張る

  4. 元のDAG上で頂点 $i$ から頂点 $j$ へ有向辺が存在するなら、 頂点 $i$ から頂点 $j’$ へ容量1の辺を張る

  5. $\text{source}$ から $\text{sink}$ への最大流 $F$ を求める。

  6. $\mid V\mid - \mid F\mid$ が解である。

大雑把に言うとマッチングの辺の数がDAG上のパスの始点で無い頂点の個数と一致するため、これを最大化するとパスの個数が最小化される。詳しい解説は蟻本p242 Stock Chartsが詳しい。

これに重みをつけるのは簡単で、 $4$ で張る辺にマトリョーシカ $j$ の体積をコストにすれば良い。

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2828"

#include "../../Src/Graph/Flow/SuccessiveShortestPath.hpp"
#include "../../Src/Template/IOSetting.hpp"

#include <algorithm>
#include <iostream>
#include <numeric>

bool solve() {
    using namespace zawa;
    int n; std::cin >> n;
    if (n == 0) return false;
    std::vector<std::array<int, 3>> a(n);
    for (auto& x : a) {
        for (auto& v : x) std::cin >> v;
        std::sort(x.begin(), x.end());
    }
    SuccessiveShortestPath<int, int> mcf(2 * n + 2);
    int source{2 * n}, sink{source + 1};
    for (int i{} ; i < n ; i++) {
        mcf.addEdge(source, i, 1, 0);
        mcf.addEdge(n + i, sink, 1, 0);
    }
    std::vector<int> big(n);
    for (int i{} ; i < n ; i++) {
        big[i] = a[i][0] * a[i][1] * a[i][2];
    }
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < n ; j++) {
            bool ok{true};
            for (int k{} ; k < 3 ; k++) ok &= a[i][k] > a[j][k];
            if (ok) {
                mcf.addEdge(i, n + j, 1, -big[j]);
            }
        }
    }
    mcf.dagdp(source, sink);
    mcf.updatePotential();
    int sum{std::accumulate(big.begin(), big.end(), 0)};
    int ans{sum};
    for (const auto& flow : mcf.slope(source, sink)) {
        ans = std::min(ans, sum + flow);
    }
    std::cout << ans << '\n';
    return true;
}

int main() {
    while (solve()) ;
}
#line 1 "Test/AOJ/2828.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2828"

#line 2 "Src/Graph/Flow/SuccessiveShortestPath.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Utility/U32Pair.hpp"

#line 4 "Src/Utility/U32Pair.hpp"

#include <functional>
#include <iostream>

namespace zawa {

class U32Pair {
private:
    static constexpr u32 SHIFT{32};
    static constexpr u32 MASK{static_cast<u32>((1LL << SHIFT) - 1)};
    u64 value_{};
public:
    constexpr U32Pair() {}
    constexpr U32Pair(u32 first, u32 second) {
        value_ = (static_cast<u64>(first) << SHIFT) | second;
    }
    constexpr u32 first() const noexcept {
        return static_cast<u32>(value_ >> SHIFT);
    }
    constexpr u32 second() const noexcept {
        return static_cast<u32>(value_ & MASK);
    }
    constexpr u64 combined() const noexcept {
        return value_;
    }
    constexpr U32Pair& operator=(const U32Pair& rhs) {
        value_ = rhs.value_;
        return *this;
    }
    friend constexpr bool operator==(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ == rhs.value_;
    }
    friend constexpr bool operator!=(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ != rhs.value_;
    }
    friend constexpr bool operator<(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ < rhs.value_;
    }
    friend constexpr bool operator<=(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ <= rhs.value_;
    }
    friend constexpr bool operator>(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ > rhs.value_;
    }
    friend constexpr bool operator>=(const U32Pair& lhs, const U32Pair& rhs) {
        return lhs.value_ >= rhs.value_;
    }
    friend std::ostream& operator<<(std::ostream& os, const U32Pair& pair) {
        os << '(' << pair.first() << ',' << pair.second() << ')';
        return os;
    }
};

struct U32PairHash {
    usize operator()(const U32Pair& pair) const noexcept {
        return std::hash<u64>{}(pair.combined());
    }
};

} // namespace zawa
#line 5 "Src/Graph/Flow/SuccessiveShortestPath.hpp"

#include <cassert>
#include <limits>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>

namespace zawa {

template <class Cap, class Cost>
class SuccessiveShortestPath {
public:
    static_assert(std::is_signed_v<Cost>, U"Cost must be signed");
    static constexpr Cost invalid{(std::numeric_limits<Cost>::max() >> 1) - 1};
    static constexpr u32 reverseId(u32 i) noexcept {
        return i ^ 1;
    }

    struct Edge {
        u32 from{}, to{};
        Cap residual{};
        Cost cost{};
        Edge() = default;
        Edge(u32 from, u32 to, const Cap& cap, const Cost& cost)
            : from{from}, to{to}, residual{cap}, cost{cost} {}
    };

    usize n_{}, m_{};
    std::vector<Edge> edges_;
    std::vector<std::vector<u32>> g_;
    std::vector<Cost> dist_, potential_;
    std::vector<U32Pair> prev_;
    Cost mcf_{};

    constexpr usize size() const noexcept {
        return n_;
    }
    constexpr usize edgeSize() const noexcept {
        return m_;
    }
    
    SuccessiveShortestPath() = default;
    SuccessiveShortestPath(usize n, usize m = usize{}) 
        : n_{n}, m_{}, edges_{}, g_(n), dist_(n), potential_(n), prev_(n), mcf_{} {
        g_.shrink_to_fit();
        dist_.shrink_to_fit();
        potential_.shrink_to_fit();
        prev_.shrink_to_fit();
        edges_.reserve(2 * m);
    }

    void emplace(u32 from, u32 to, const Cap& cap, const Cost& cost) {
        g_[from].emplace_back(m_);
        edges_.emplace_back(from, to, cap, cost);
        m_++;
    }

    u32 addEdge(u32 from, u32 to, const Cap& cap, const Cost& cost) {
        assert(from < size());
        assert(to < size());
        u32 res{static_cast<u32>(m_)};
        emplace(from, to, cap, cost);
        emplace(to, from, Cap{}, -cost);
        return res;
    }

    inline u32 from(u32 i) const noexcept {
        return edges_[i].from;
    }
    inline u32 to(u32 i) const noexcept {
        return edges_[i].to;
    }
    inline const Cap& residual(u32 i) const noexcept {
        return edges_[i].residual;
    }
    inline const Cost& cost(u32 i) const noexcept {
        return edges_[i].cost;
    }
    inline const Cap& flowed(u32 i) const noexcept {
        assert(i < edgeSize());
        return residual(i ^ 1);
    }
    inline const Cap& capcacity(u32 i) const noexcept {
        assert(i < edgeSize());
        return residual(i) + flowed(i);
    }

    inline Cost edgeCost(u32 i) const noexcept {
        return potential_[from(i)] + cost(i) - potential_[to(i)];
    }
    bool relax(u32 i) {
        if (residual(i) > 0 and dist_[to(i)] > dist_[from(i)] + edgeCost(i)) {
            dist_[to(i)] = dist_[from(i)] + edgeCost(i);
            prev_[to(i)] = U32Pair{from(i), i};
            return true;
        }
        return false;
    }

    bool dijkstra(u32 s, u32 t) {
        assert(s < size());
        assert(t < size());
        std::fill(dist_.begin(), dist_.end(), invalid);
        dist_[s] = Cost{};
        using qt = std::pair<Cost, u32>;
        std::priority_queue<qt, std::vector<qt>, std::greater<qt>> que;
        que.emplace(dist_[s], s);
        while (que.size()) {
            auto [d, v]{que.top()};
            que.pop();
            if (dist_[v] < d) continue;
            for (u32 i : g_[v]) {
                if (relax(i)) {
                    que.emplace(dist_[to(i)], to(i));
                }
            }
        }
        return dist_[t] < invalid;
    }

    bool dagdp(u32 s, u32 t) {
        assert(s < size());
        assert(t < size());
        std::fill(dist_.begin(), dist_.end(), invalid);
        dist_[s] = Cost{};
        std::vector<u32> ord;
        ord.reserve(size());
        std::vector<bool> vis(size());
        vis[s] = true;
        ord.push_back(s);
        for (u32 i{} ; i < ord.size() ; i++) {
            u32 v{ord[i]};
            for (auto e : g_[v]) {
                if (!vis[to(e)]) {
                    ord.push_back(to(e));
                    vis[to(e)] = true;
                }
                relax(e);
            }
        }
        return dist_[t] < invalid;
    }

    bool bellmanford(u32 s, u32 t) {
        assert(s < size());
        assert(t < size());
        std::fill(dist_.begin(), dist_.end(), invalid);
        dist_[s] = Cost{};
        for (u32 i{} ; i + 1 < size() ; i++) {
            for (u32 j{} ; j < edgeSize() ; j++) {
                relax(j);
            }
        }
        return dist_[t] < invalid;
    }

    void updatePotential() {
        for (u32 v{} ; v < size() ; v++) {
            potential_[v] = potential_[v] + (dist_[v] == invalid ? Cost{} : dist_[v]);
        }
    }

    Cap flush(u32 s, u32 t, Cap up = std::numeric_limits<Cap>::max()) {
        for (u32 v{t} ; v != s ; v = prev_[v].first()) {
            up = std::min(up, residual(prev_[v].second()));
        }
        for (u32 v{t} ; v != s ; v = prev_[v].first()) {
            edges_[prev_[v].second()].residual -= up;
            edges_[prev_[v].second() ^ 1].residual += up;
        }
        return up;
    }

    bool flow(u32 s, u32 t, Cap flow) {
        assert(s < size());
        assert(t < size());
        while (flow > 0 and dijkstra(s, t)) {
            updatePotential();
            Cap water{flush(s, t, flow)};
            mcf_ += potential_[t] * water;
            flow -= water;
        }
        return flow == 0;
    }

    Cap maxflow(u32 s, u32 t) {
        assert(s < size());
        assert(t < size());
        Cap flow{};
        while (dijkstra(s, t)) {
            updatePotential();
            Cap water{flush(s, t)};
            mcf_ += potential_[t] * water;
            flow += water;
        }
        return flow;
    }

    std::vector<Cost> slope(u32 s, u32 t) {
        assert(s < size());
        assert(t < size());
        Cap flow{};
        std::vector<Cost> res;
        while (dijkstra(s, t)) {
            updatePotential();
            Cap water{flush(s, t)};
            for (u32 i{} ; i < water ; i++) {
                res.emplace_back(mcf_);
                mcf_ += potential_[t];
                flow++;
            }
        }
        res.emplace_back(mcf_);
        return res;
    }

    struct Line {
        Cap dn{}, up{};
        Cost slope{};
        Line() = default;
        Line(Cap dn, Cap up, Cost slope) : dn{dn}, up{up}, slope{slope} {}
    };
    std::vector<Line> slopeACL(u32 s, u32 t) {
        assert(s < size());
        assert(t < size()); 
        Cap flow{};
        std::vector<Line> res;
        while (dijkstra(s, t)) {
            updatePotential();
            Cap water{flush(s, t)};
            mcf_ += potential_[t] * water;
            res.emplace_back(flow, flow + water, potential_[t]);
            flow += water;
        }
        return res;
    }

    Cost minCost() const noexcept {
        return mcf_;
    }
};

} // namespace zawa
#line 2 "Src/Template/IOSetting.hpp"

#line 4 "Src/Template/IOSetting.hpp"

#line 6 "Src/Template/IOSetting.hpp"
#include <iomanip>

namespace zawa {

void SetFastIO() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
}

void SetPrecision(u32 dig) {
    std::cout << std::fixed << std::setprecision(dig);
}

} // namespace zawa
#line 5 "Test/AOJ/2828.test.cpp"

#include <algorithm>
#line 8 "Test/AOJ/2828.test.cpp"
#include <numeric>

bool solve() {
    using namespace zawa;
    int n; std::cin >> n;
    if (n == 0) return false;
    std::vector<std::array<int, 3>> a(n);
    for (auto& x : a) {
        for (auto& v : x) std::cin >> v;
        std::sort(x.begin(), x.end());
    }
    SuccessiveShortestPath<int, int> mcf(2 * n + 2);
    int source{2 * n}, sink{source + 1};
    for (int i{} ; i < n ; i++) {
        mcf.addEdge(source, i, 1, 0);
        mcf.addEdge(n + i, sink, 1, 0);
    }
    std::vector<int> big(n);
    for (int i{} ; i < n ; i++) {
        big[i] = a[i][0] * a[i][1] * a[i][2];
    }
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < n ; j++) {
            bool ok{true};
            for (int k{} ; k < 3 ; k++) ok &= a[i][k] > a[j][k];
            if (ok) {
                mcf.addEdge(i, n + j, 1, -big[j]);
            }
        }
    }
    mcf.dagdp(source, sink);
    mcf.updatePotential();
    int sum{std::accumulate(big.begin(), big.end(), 0)};
    int ans{sum};
    for (const auto& flow : mcf.slope(source, sink)) {
        ans = std::min(ans, sum + flow);
    }
    std::cout << ans << '\n';
    return true;
}

int main() {
    while (solve()) ;
}
Back to top page