結果

問題 No.2604 Initial Motion
ユーザー Aeren
提出日時 2024-01-12 22:58:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 452 ms / 3,000 ms
コード長 5,095 bytes
コンパイル時間 2,962 ms
コンパイル使用メモリ 262,272 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-27 23:45:06
合計ジャッジ時間 11,429 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
template<class T, class C>
struct weighted_flow_network{
    struct E{
        int from, to;
        T capacity, flow;
        C cost;
    };
    vector<vector<int>> adj;
    vector<E> edge;
    int n;
    C cost = 0;
    weighted_flow_network(int n): n(n), adj(n){ }
    void clear_flow(){
        for(auto &e: edge) e.flow = 0;
        cost = 0;
    }
    int insert(int from, int to, T forward_cap, T backward_cap, C cost){
        assert(0 <= from && from < n && 0 <= to && to < n);
        int ind = (int)edge.size();
        adj[from].push_back((int)edge.size());
        edge.push_back({from, to, forward_cap, 0, cost});
        adj[to].push_back((int)edge.size());
        edge.push_back({to, from, backward_cap, 0, -cost});
        return ind;
    }
    void add_flow(int i, T f){
        edge[i].flow += f;
        cost += f * edge[i].cost;
        edge[i ^ 1].flow -= f;
    }
    friend ostream &operator<<(ostream &out, const weighted_flow_network &F){
        out << "\n";
        for(auto &e: F.edge){
            out << "{" << e.from << " -> " << e.to << ", " << e.cost << ", " << e.flow << "/" << e.capacity << "}\n";
        }
        return out;
    }
};
// Requires weighted_flow_network
template<class T, class C>
struct minimum_cost_maximum_flow_spfa{
    static constexpr T eps = (T) 1e-9;
    weighted_flow_network<T, C> &F;
    minimum_cost_maximum_flow_spfa(weighted_flow_network<T, C> &F): F(F), d(F.n), in_queue(F.n), pe(F.n), state(F.n){ }
    // type 0: augment as long as a path exists
    // type 1: augment as long as a negative cost path exists
    vector<C> d;
    vector<int> in_queue, q, pe;
    T expath(int source, int sink, bool type = false){
        fill(d.begin(), d.end(), numeric_limits<C>::max());
        q = {source};
        d[source] = 0;
        in_queue[source] = true;
        int beg = 0;
        bool found = false;
        while(beg < (int)q.size()){
            int u = q[beg ++];
            if(u == sink) found = true;
            in_queue[u] = false;
            for(auto id: F.adj[u]){
                auto &e = F.edge[id];
                if(e.capacity - e.flow > eps && d[u] + e.cost < d[e.to]){
                    d[e.to] = d[u] + e.cost;
                    pe[e.to] = id;
                    if(!in_queue[e.to]){
                        q.push_back(e.to);
                        in_queue[e.to] = true;
                    }
                }
            }
        }
        if(found){
            T push = numeric_limits<T>::max();
            int u = sink;
            while(u != source){
                auto &e = F.edge[pe[u]];
                push = min(push, e.capacity - e.flow);
                u = e.from;
            }
            u = sink;
            assert(push >= 0);
            if(type && d[sink] >= 0) return false;
            while(u != source){
                F.add_flow(pe[u], push);
                u = F.edge[pe[u]].from;
            }
            return push;
        }
        return 0;
    }
    vector<int> stack, state;
    bool try_cycle_cancelling(){
        fill(d.begin(), d.end(), 0);
        q.resize(F.n);
        iota(q.begin(), q.end(), 0);
        fill(in_queue.begin(), in_queue.end(), false);
        fill(pe.begin(), pe.end(), -1);
        int beg = 0, iter = 0;
        auto detect_cycle = [&]()->bool{
            stack.clear();
            fill(state.begin(), state.end(), 0);
            for(auto s = 0; s < F.n; ++ s){
                if(state[s]) continue;
                for(auto u = s; ; ){
                    if(state[u]){
                        if(state[u] == 1){
                            stack.erase(stack.begin(), find(stack.begin(), stack.end(), u));
                            assert(!stack.empty() && stack[0] == u);
                            T flow = numeric_limits<T>::max();
                            for(auto u: stack){
                                auto &e = F.edge[pe[u]];
                                flow = min(flow, e.capacity - e.flow);
                            }
                            for(auto u: stack) F.add_flow(pe[u], flow);
                            return true;
                        }
                        break;
                    }
                    stack.push_back(u);
                    state[u] = 1;
                    if(!~pe[u]) break;
                    u = F.edge[pe[u]].from;
                }
                for(auto u: stack) state[u] = 2;
                stack.clear();
            }
            return false;
        };
        while(beg < (int)q.size()){
            int u = q[beg ++];
            in_queue[u] = false;
            for(auto id: F.adj[u]){
                auto &e = F.edge[id];
                if(e.capacity - e.flow > eps && d[u] + e.cost < d[e.to]){
                    d[e.to] = d[u] + e.cost;
                    pe[e.to] = id;
                    if(++ iter == F.n){
                        iter = 0;
                        if(detect_cycle()) return true;
                    }
                    if(!in_queue[e.to]){
                        q.push_back(e.to);
                        in_queue[e.to] = true;
                    }
                }
            }
        }
        return detect_cycle();
    }
    // type 0: min cost max flow
    // type 1: min cost flow
    // O(Augmenting_Paths * SPFA), additional O(SPFA * Cycle_cnt) if negative cycle exists
    pair<T, C> solve(int source, int sink, bool type = false, bool negative_cycle_presence = false){
        F.clear_flow();
        if(negative_cycle_presence) while(try_cycle_cancelling());
        T flow = 0;
        for(T delta; delta = expath(source, sink, type); flow += delta);
        return {flow, F.cost};
    }
};
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(ios::badbit | ios::failbit);
    int np, n, m;
    cin >> np >> n >> m;
    weighted_flow_network<int, long long> F(n + 2);
    int source = n, sink = n + 1;
    for(auto i = 0; i < np; ++ i){
        int p;
        cin >> p, -- p;
        F.insert(source, p, 1, 0, 0);
    }
    for(auto u = 0; u < n; ++ u){
        int cap;
        cin >> cap;
        F.insert(u, sink, cap, 0, 0);
    }
    for(auto i = 0; i < m; ++ i){
        int u, v;
        long long d;
        cin >> u >> v >> d, -- u, -- v;
        F.insert(u, v, np, 0, d);
        F.insert(v, u, np, 0, d);
    }
    cout << minimum_cost_maximum_flow_spfa(F).solve(source, sink).second << "\n";
    return 0;
}
/*
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0