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: AtCoder Library Practice Contest - E MinCostFlow
(Test/Manual/practice2_e.test.cpp)

知らなかったテクがあった。

最小費用流に帰着するが、最小費用最大流ではない( $NK$ 流すのが最適とは限らない )

こういう時はsourceからsinkに向けて容量無限、コスト $0$ の辺を張ると良い。

今回は最大化問題を最小化問題に変換するために(コストをマイナス1倍しており、負コストを解消するため)下駄を履かせているので、この辺にも下駄を履かせること

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

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

#include <iostream>
#include <string>
#include <vector>

/*
 * AtCoder Library Practice Contest - E MinCostFlow
 * https://atcoder.jp/contests/practice2/submissions/49008995
 */

void solve() {
    using namespace zawa;
    SetFastIO();
    int n, k; std::cin >> n >> k;
    SuccessiveShortestPath<int, long long> mcf(2 * n + 2);
    int source{2 * n}, sink{2 * n + 1};
    for (int i{} ; i < n ; i++) {
        mcf.addEdge(source, i, k, 0);
        mcf.addEdge(n + i, sink, k, 0);
    }
    const long long INF{(long long)1e9};
    std::vector A(n, std::vector<int>(n));
    std::vector id(n, std::vector<int>(n));
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < n ; j++) {
            int a; std::cin >> a;
            A[i][j] = a;
            a = INF - a;
            id[i][j] = mcf.addEdge(i, n + j, 1, a);
        }
    }
    mcf.addEdge(source, sink, INF, INF);
    assert(mcf.flow(source, sink, n * k));
    std::vector S(n, std::string(n, '.'));
    long long ans{};
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < n ; j++) {
            if (mcf.flowed(id[i][j])) {
                ans += A[i][j];
                S[i][j] = 'X';
            }
        }
    }
    std::cout << ans << '\n';
    for (int i{} ; i < n ; i++) {
        std::cout << S[i] << '\n';
    }
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
#line 1 "Test/Manual/practice2_e.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/Template/IOSetting.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 4 "Src/Template/IOSetting.hpp"

#include <iostream>
#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 2 "Src/Graph/Flow/SuccessiveShortestPath.hpp"

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

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

#include <functional>
#line 7 "Src/Utility/U32Pair.hpp"

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 5 "Test/Manual/practice2_e.test.cpp"

#line 7 "Test/Manual/practice2_e.test.cpp"
#include <string>
#line 9 "Test/Manual/practice2_e.test.cpp"

/*
 * AtCoder Library Practice Contest - E MinCostFlow
 * https://atcoder.jp/contests/practice2/submissions/49008995
 */

void solve() {
    using namespace zawa;
    SetFastIO();
    int n, k; std::cin >> n >> k;
    SuccessiveShortestPath<int, long long> mcf(2 * n + 2);
    int source{2 * n}, sink{2 * n + 1};
    for (int i{} ; i < n ; i++) {
        mcf.addEdge(source, i, k, 0);
        mcf.addEdge(n + i, sink, k, 0);
    }
    const long long INF{(long long)1e9};
    std::vector A(n, std::vector<int>(n));
    std::vector id(n, std::vector<int>(n));
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < n ; j++) {
            int a; std::cin >> a;
            A[i][j] = a;
            a = INF - a;
            id[i][j] = mcf.addEdge(i, n + j, 1, a);
        }
    }
    mcf.addEdge(source, sink, INF, INF);
    assert(mcf.flow(source, sink, n * k));
    std::vector S(n, std::string(n, '.'));
    long long ans{};
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < n ; j++) {
            if (mcf.flowed(id[i][j])) {
                ans += A[i][j];
                S[i][j] = 'X';
            }
        }
    }
    std::cout << ans << '\n';
    for (int i{} ; i < n ; i++) {
        std::cout << S[i] << '\n';
    }
}

int main() {
#ifdef ATCODER
    solve();
#else
    std::cout << "Hello World" << '\n';
#endif
}
Back to top page