結果

問題 No.2604 Initial Motion
コンテスト
ユーザー zawakasu
提出日時 2024-01-14 01:08:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,004 ms / 3,000 ms
コード長 9,792 bytes
コンパイル時間 2,739 ms
コンパイル使用メモリ 213,408 KB
最終ジャッジ日時 2025-02-18 19:54:10
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>




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


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




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

#include <type_traits>

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
using namespace zawa;

int main() {
    SetFastIO();

    int k, n, m; std::cin >> k >> n >> m;
    SuccessiveShortestPath<int, long long> mcf(n + 2);
    int source{n}, sink{n + 1};
    for (int i{} ; i < k ; i++) {
        int a; std::cin >> a;
        a--;
        mcf.addEdge(source, a, 1, 0LL);
    }
    for (int i{} ; i < n ; i++) {
        int b; std::cin >> b;
        mcf.addEdge(i, sink, b, 0LL);
    }
    for (int _{} ; _ < m ; _++) {
        int u, v; std::cin >> u >> v;
        u--; v--;
        long long d; std::cin >> d;
        mcf.addEdge(u, v, k, d);
        mcf.addEdge(v, u, k, d);
    }
    assert(mcf.maxflow(source, sink) == k);
    long long ans{mcf.minCost()};
    std::cout << ans << '\n';
}
0