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: AOJ2872 最短距離を伸ばすえびちゃん
(Test/AOJ/2872.test.cpp)

明らかに各辺に対して1伸ばすか全く伸ばさないかを考えれば良い(2伸ばすことが最適になることはありえない)

$s-t$ パスの最短経路になりうる辺はDijkstra法で列挙できる(最短経路木の構築と同様にすることで、最短経路DAGみたいなものを作る。そんな用語があるかは知らないが)

そのようなDAGに対して $s-t$ カット $(s, t)$ を考える。 $s$ 側のある頂点と $t$ 側のある頂点を結ぶ辺全てを1伸ばすとき $s-t$ 間最短経路も1伸ばすことができる。

そのコストはカット容量 $c(s, t)$ と一致する。以上より、最小カット問題に帰着して、DAG上の最大流を求めれば良い。面白いなぁ。

Depends on

Code

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

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Graph/ShortestPath/Dijkstra.hpp"
#include "../../Src/Graph/Flow/Dinic.hpp"

#include <cassert>
#include <iostream>
#include <tuple>
#include <vector>

int main() {
    using namespace zawa;
    int n, m, s, t; std::cin >> n >> m >> s >> t;
    s--; t--;
    Dijkstra<unsigned> g(n);
    std::vector<std::tuple<int, int, int, int>> e(m);
    for (auto& [u, v, d, c] : e) {
        std::cin >> u >> v >> d >> c;
        u--; v--;
        g.addDirectedEdge(u, v, (unsigned)d);
    }
    auto tree{g.build(s)};
    assert(tree.connect(t));
    Dinic<int> mf(n);
    for (auto [u, v, d, c] : e) {
        if (!tree.connect(u)) continue;
        if (tree[u] + d == tree[v]) {
            mf.addEdge(u, v, c);
        }
    }
    int ans{mf.flow(s, t)};
    std::cout << ans << '\n';
}
#line 1 "Test/AOJ/2872.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2872"

#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/ShortestPath/Dijkstra.hpp"

#line 2 "Src/Graph/ShortestPath/WeightedShortestPathTree.hpp"

#line 2 "Src/Graph/ShortestPath/Edge.hpp"

#line 4 "Src/Graph/ShortestPath/Edge.hpp"

namespace zawa {

namespace internal {

class Edge {
protected:
    static constexpr u32 INVALID{static_cast<u32>(-1)};
public:
    u32 parent{INVALID}; 
    u32 id{INVALID};
    Edge() = default;
    Edge(u32 parent, u32 id) : parent{parent}, id{id} {}
    Edge& operator=(const Edge& edge) {
        parent = edge.parent;
        id = edge.id;
        return *this;
    }
    inline bool exist() const noexcept {
        return parent != INVALID;
    }
    static constexpr u32 invalid() noexcept {
        return INVALID; 
    }
};

template <class Weight>
class WeightedEdge : public Edge {
public:
    Weight weight{INVALID};
    WeightedEdge() = default;
    WeightedEdge(u32 parent, const Weight& weight, u32 id)
        : Edge{parent, id}, weight{weight} {}

    WeightedEdge& operator=(const WeightedEdge& edge) {
        parent = edge.parent;
        id = edge.id;
        weight = edge.weight;
        return *this;
    }

};

} // namespace internal

} // namespace zawa
#line 5 "Src/Graph/ShortestPath/WeightedShortestPathTree.hpp"

#include <algorithm>
#include <cassert>
#include <type_traits>
#include <vector>

namespace zawa {

namespace internal {

template <class Weight>
class WeightedShortestPathTree {
public:
    static_assert(std::is_unsigned_v<Weight>, "Dijkstra's Algorithm only be work well by unsigned weight");
    using E = WeightedEdge<Weight>;
    static constexpr u32 invalid() noexcept {
        return E::invalid();
    }
private:
    static constexpr u32 INVALID{E::invalid()};
    usize n_;
    u32 root_;
    std::vector<E> tree_;
    std::vector<Weight> dist_;
public:
    WeightedShortestPathTree() = default;
    WeightedShortestPathTree(u32 n, u32 root) 
        : n_{n}, root_{root}, tree_(n), dist_(n, static_cast<Weight>(-1)) {
        assert(root < n);
        tree_.shrink_to_fit();
        dist_.shrink_to_fit();
        dist_[root] = Weight{};
    }

    inline usize size() const noexcept {
        return n_;
    }
    inline u32 root() const noexcept {
        return root_;
    }
    inline u32 parent(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].parent;
    }
    inline u32 id(u32 v) const noexcept {
        assert(v < size());
        return tree_[v].id;
    }
    inline bool connect(u32 v) const noexcept {
        assert(v < size());
        return v == root_ or tree_[v].exist();
    }
    inline const Weight& dist(u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    const Weight& operator[](u32 v) const noexcept {
        assert(v < size());
        return dist_[v];
    }

    bool relax(u32 from, u32 to, const Weight& weight, u32 id) {
        if (dist_[to] > dist_[from] + weight) {
            dist_[to] = dist_[from] + weight;
            tree_[to].parent = from;
            tree_[to].id = id;
            return true;
        }
        return false;
    }

    std::vector<u32> pathV(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<u32> res(1);
        res[0] = v;
        while (parent(v) != invalid()) {
            v = parent(v);
            res.emplace_back(v);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }

    std::vector<E> pathE(u32 v) {
        assert(v < size());
        assert(connect(v));
        std::vector<E> res;
        while (v != root()) {
            res.emplace_back(tree_[v]);
            v = parent(v);
        }
        std::reverse(res.begin(), res.end());
        return res;
    }
};

} // namespace internal

} // namespace zawa
#line 5 "Src/Graph/ShortestPath/Dijkstra.hpp"

#line 7 "Src/Graph/ShortestPath/Dijkstra.hpp"
#include <queue>
#include <tuple>
#include <utility>
#line 11 "Src/Graph/ShortestPath/Dijkstra.hpp"

namespace zawa {

template <class Weight>
class Dijkstra {
public:
    using ShortestPathTree = internal::WeightedShortestPathTree<Weight>;
private:
    usize n_;
    std::vector<std::vector<std::tuple<u32, Weight, u32>>> adj_;

    static constexpr u32 invalid() noexcept {
        return ShortestPathTree::invalid();
    }

public:
    Dijkstra() = default;
    Dijkstra(usize n) : n_{n}, adj_(n) {
        adj_.shrink_to_fit();
    }
    usize size() const noexcept {
        return n_;
    }
    Dijkstra(const std::vector<std::pair<u32, Weight>>& g) : n_{g.size()}, adj_(g.size()) {
        adj_.shrink_to_fit();
        for (u32 v{} ; v < size() ; v++) {
            for (auto [x, w] : g[v]) {
                adj_[v].emplace_back(x, w, invalid);
            }
        }
    }
    void addDirectedEdge(u32 from, u32 to, const Weight& weight, u32 id = invalid()) {
        assert(from < size());
        assert(to < size());
        adj_[from].emplace_back(to, weight, id);
    }
    void addUndirectedEdge(u32 u, u32 v, const Weight& weight, u32 id = invalid()) {
        assert(u < size());
        assert(v < size());
        adj_[u].emplace_back(v, weight, id);
        adj_[v].emplace_back(u, weight, id);
    }

    ShortestPathTree build(u32 start) {
        using QueueData = std::pair<Weight, u32>;
        std::priority_queue<QueueData, std::vector<QueueData>, std::greater<QueueData>> queue;
        queue.emplace(Weight{}, start);
        ShortestPathTree res(n_, start);
        while (queue.size()) {
            auto [w, v]{queue.top()};
            queue.pop();
            if (res.dist(v) < w) {
                continue;
            }
            for (auto [x, w, id] : adj_[v]) {
                if (res.relax(v, x, w, id)) {
                    queue.emplace(res.dist(x), x);
                }
            } 
        }
        return res;
    }
};

} // namespace zawa
#line 2 "Src/Graph/Flow/Dinic.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/Dinic.hpp"

#line 8 "Src/Graph/Flow/Dinic.hpp"
#include <limits>
#line 12 "Src/Graph/Flow/Dinic.hpp"

namespace zawa {

template <class Cap> 
class Dinic {
private:
    static_assert(std::is_signed_v<Cap>, "Cap must be signed");
    usize n_{}, m_{};
    static constexpr u32 invalid() noexcept {
        return std::numeric_limits<u32>::max();
    }
public:
    inline usize size() const noexcept {
        return n_;
    }
    inline usize edgeNumber() const noexcept {
        return m_;
    }
private:
    struct Edge {
        u32 to{}, rev{};
        Cap residual{};
        Edge() = default;
        Edge(u32 to, u32 rev, const Cap& residual) 
            : to{to}, rev{rev}, residual{residual} {}
    };

    std::vector<std::vector<Edge>> g_;
    std::vector<U32Pair> edges_;
    std::vector<u32> label_, cur_;

    bool dualStep(u32 s, u32 t) {
        std::fill(label_.begin(), label_.end(), invalid());
        label_[s] = 0;
        std::queue<u32> queue{ { s } };
        while (queue.size()) {
            u32 v{queue.front()};
            queue.pop();
            for (const Edge& e : g_[v]) if (e.residual > 0) {
                if (label_[e.to] > label_[v] + 1) {
                    label_[e.to] = label_[v] + 1;
                    if (e.to == t) return true;
                    queue.emplace(e.to);
                }
            }
        }
        return false;
    }

    bool admissible(u32 v, const Edge& e) const noexcept {
        return e.residual > 0 and label_[v] + 1 == label_[e.to];
    }

    inline void flow(Edge& e, Cap f) {
        e.residual -= f;
        g_[e.to][e.rev].residual += f;
    }

    Cap dfs(u32 v, u32 t, Cap up) {
        if (v == t) return up;
        Cap res{};
        for (u32& i{cur_[v]} ; i < g_[v].size() ; i++) {
            if (!admissible(v, g_[v][i])) continue;
            Cap f{dfs(g_[v][i].to, t, std::min(g_[v][i].residual, up - res))};
            if (f == 0) continue;
            flow(g_[v][i], f);
            res += f;
            if (res == up) return res;
        }
        return res;
    }

    Cap primalStep(u32 s, u32 t) {
        std::fill(cur_.begin(), cur_.end(), 0u);
        cur_[t] = g_[t].size();
        Cap res{};
        while (true) {
            Cap f{dfs(s, t, std::numeric_limits<Cap>::max())};
            if (f == 0) break;
            res += f;
        }
        return res;
    }

    const Edge& edge(u32 i) const noexcept {
        return g_[edges_[i].first()][edges_[i].second()];
    }
    const Edge& reverse(u32 i) const noexcept {
        const Edge& e{edge(i)};
        return g_[e.to][e.rev];
    }

public:
    Dinic() = default;
    Dinic(u32 n, u32 m = 0u) 
        : n_{n}, m_{m}, g_(n), edges_{}, label_(n), cur_(n) {
        g_.shrink_to_fit();
        label_.shrink_to_fit();
        cur_.shrink_to_fit();
        edges_.reserve(m);
    }

    u32 addEdge(u32 u, u32 v, const Cap& cap) {
        assert(u < size());
        assert(v < size());
        u32 id{static_cast<u32>(g_[u].size())};
        u32 revId{u == v ? id + 1 : static_cast<u32>(g_[v].size())};
        u32 res{static_cast<u32>(edges_.size())};
        edges_.emplace_back(u, id);
        g_[u].emplace_back(v, revId, cap);
        g_[v].emplace_back(u, id, Cap{});
        m_++;
        return res;
    }

    const Cap& flowed(u32 id) const noexcept {
        assert(id < edgeNumber());
        return reverse(id).residual;
    }
    const Cap& residual(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edge(id).residual;
    }
    const Cap& capacity(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edge(id).residual + reverse(id).residual;
    }
    const u32& from(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edges_[id].first();
    }
    const u32& to(u32 id) const noexcept {
        assert(id < edgeNumber());
        return edge(id).to;
    }

    Cap flow(u32 s, u32 t) {
        assert(s < size());
        assert(t < size()); 
        Cap res{};
        while (dualStep(s, t)) {
            res += primalStep(s, t);
        }
        return res;
    }

    std::vector<bool> cut(u32 s) {
        std::vector<bool> res(size());
        res[s] = true;
        std::queue<u32> queue{ { s } };
        while (queue.size()) {
            u32 v{queue.front()};
            queue.pop();
            for (const auto& e : g_[v]) if (e.residual > 0 and !res[e.to]) {
                res[e.to] = true;
                queue.emplace(e.to);
            }
        }
        return res;
    }    
};

} // namespace zawa
#line 6 "Test/AOJ/2872.test.cpp"

#line 11 "Test/AOJ/2872.test.cpp"

int main() {
    using namespace zawa;
    int n, m, s, t; std::cin >> n >> m >> s >> t;
    s--; t--;
    Dijkstra<unsigned> g(n);
    std::vector<std::tuple<int, int, int, int>> e(m);
    for (auto& [u, v, d, c] : e) {
        std::cin >> u >> v >> d >> c;
        u--; v--;
        g.addDirectedEdge(u, v, (unsigned)d);
    }
    auto tree{g.build(s)};
    assert(tree.connect(t));
    Dinic<int> mf(n);
    for (auto [u, v, d, c] : e) {
        if (!tree.connect(u)) continue;
        if (tree[u] + d == tree[v]) {
            mf.addEdge(u, v, c);
        }
    }
    int ans{mf.flow(s, t)};
    std::cout << ans << '\n';
}
Back to top page