#943890 (C++17) No.2604 Initial Motion

提出ソース

結果

問題	No.2604 Initial Motion
ユーザー	asaringo
提出日時	2024-01-13 01:07:27
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	987 ms / 3,000 ms
コード長	9,238 bytes
コンパイル時間	2,813 ms
コンパイル使用メモリ	230,164 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2024-01-13 01:07:50
合計ジャッジ時間	22,027 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	2 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	27 ms 6,676 KB
testcase_04	AC	27 ms 6,676 KB
testcase_05	AC	27 ms 6,676 KB
testcase_06	AC	27 ms 6,676 KB
testcase_07	AC	27 ms 6,676 KB
testcase_08	AC	26 ms 6,676 KB
testcase_09	AC	26 ms 6,676 KB
testcase_10	AC	27 ms 6,676 KB
testcase_11	AC	28 ms 6,676 KB
testcase_12	AC	26 ms 6,676 KB
testcase_13	AC	868 ms 6,676 KB
testcase_14	AC	619 ms 6,676 KB
testcase_15	AC	315 ms 6,676 KB
testcase_16	AC	784 ms 6,676 KB
testcase_17	AC	987 ms 6,676 KB
testcase_18	AC	969 ms 6,676 KB
testcase_19	AC	935 ms 6,676 KB
testcase_20	AC	772 ms 6,676 KB
testcase_21	AC	626 ms 6,676 KB
testcase_22	AC	918 ms 6,676 KB
testcase_23	AC	640 ms 6,676 KB
testcase_24	AC	845 ms 6,676 KB
testcase_25	AC	940 ms 6,676 KB
testcase_26	AC	708 ms 6,676 KB
testcase_27	AC	533 ms 6,676 KB
testcase_28	AC	680 ms 6,676 KB
testcase_29	AC	844 ms 6,676 KB
testcase_30	AC	601 ms 6,676 KB
testcase_31	AC	719 ms 6,676 KB
testcase_32	AC	683 ms 6,676 KB
testcase_33	AC	156 ms 6,676 KB
testcase_34	AC	447 ms 6,676 KB
testcase_35	AC	468 ms 6,676 KB
testcase_36	AC	441 ms 6,676 KB
testcase_37	AC	202 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB
testcase_39	AC	2 ms 6,676 KB
testcase_40	AC	312 ms 6,676 KB
testcase_41	AC	298 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e ...) e
#define overload5(a, b, c, d, e, f ...) f
#define overload6(a, b, c, d, e, f, g ...) g
#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
typedef long long ll;
typedef long double ld;
#define chmin(a,b) a = min(a,b);
#define chmax(a,b) a = max(a,b);
#define bit_count(x) __builtin_popcountll(x)
#define leading_zero_count(x) __builtin_clz(x)
#define trailing_zero_count(x) __builtin_ctz(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)
#define rep1(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl;
#define print(...) printall(__VA_ARGS__);
#define debug(a) cout << #a << " " << a << endl;
#define all(a) a.begin(), a.end()
#define endl "\n";
#define v1(T,n,a) vector<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}

struct MinCostFlow{
    
    private:
        static const ll inf = LLONG_MAX;
        struct edge
        {
            int to , rev;
            ll cost , cap;
        };

        struct edge_ {
            int from, to;
            ll cap, flow , cost;
        };

        int n;
        vector<vector<edge>> G;
        vector<pair<int,int>> pos;
        vector<ll> dist , h;
        vector<int> prevv , preve;

        void init_(int n_){
            G.resize(n_);
            dist.resize(n_);
            h.resize(n_);
            prevv.resize(n_);
            preve.resize(n_);
        }

        void add_edge_(int from, int to, ll cap, ll cost){
            pos.push_back({from, G[from].size()});
            int from_id = int(G[from].size());
            int to_id = int(G[to].size());
            if (from == to) to_id++;
            G[from].push_back(edge{to, to_id, cost, cap});
            G[to].push_back(edge{from, from_id, -cost, 0});
        }

        int edge_size_(){
            return (int)pos.size();
        }

        edge_ get_edge_(int k){
            edge e = G[pos[k].first][pos[k].second];
            edge re = G[e.to][e.rev];
            return edge_{pos[k].first, e.to, e.cap + re.cap, re.cap, e.cost};
        }

        vector<edge_> get_edges_(){
            int m = (int)pos.size();
            vector<edge_> res;
            for(int i = 0; i < m; i++) res.push_back(get_edge_(i));
            return res;
        }

        vector<pair<ll,ll>> min_flow_(int s, int t, ll flow_limit){
            vector<pair<ll,ll>> res = {{0,0}};
            ll flow = 0;
            ll cost = 0;
            ll prev_cost_per_flow = -1;
            fill(h.begin(), h.end(),0);
            while(flow < flow_limit){
                fill(dist.begin(),dist.end(),9223372036854775807LL);
                priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> que;
                dist[s] = 0;
                que.push(pair<ll,int>(0,s));
                while(!que.empty()){
                    pair<ll,int> p = que.top(); que.pop();
                    int v = p.second;
                    if(dist[v] < p.first) continue;
                    for(int i = 0; i < G[v].size(); i++){
                        edge e = G[v][i];
                        if(e.cap > 0 && dist[e.to] > dist[v] + h[v] - h[e.to] + e.cost){
                            dist[e.to] = dist[v] + h[v] - h[e.to] + e.cost;
                            prevv[e.to] = v;
                            preve[e.to] = i;
                            que.push(pair<ll,int>(dist[e.to],e.to));
                        }
                    }
                }
                if(dist[t] == inf) break; // 総流量fを流すことができなかった
                for(int i = 0; i < n; i++) h[i] += dist[i];
                ll d = flow_limit - flow;
                for(int v = t; v != s; v = prevv[v]) d = min(d,G[prevv[v]][preve[v]].cap);
                for(int v = t; v != s; v = prevv[v]){
                    edge &e = G[prevv[v]][preve[v]];
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                }
                cost += h[t] * d;
                flow += d;
                if(prev_cost_per_flow == h[t]) res.pop_back();
                res.push_back({flow, cost});
                prev_cost_per_flow = h[t];
            }
            return res;
        }
    
    public:
        MinCostFlow() {}
        MinCostFlow(int n_): n(n_) { init_(n); }
        void init(int n) { init_(n); }
        int edge_size() { return edge_size_(); }
        void add_edge(int from , int to , ll cap, ll cost) { add_edge_(from, to, cap, cost); }
        edge_ get_edge(int k) { return get_edge_(k); }
        vector<edge_> get_edges() { return get_edges_(); }
        ll min_cost(int s, int t, ll flow_limit = inf){ return min_flow_(s,t,flow_limit).back().second; }
        pair<ll,ll> min_cost_flow(int s, int t, ll flow_limit = inf){ return min_flow_(s,t,flow_limit).back(); }
        vector<pair<ll,ll>> slope(int s, int t, ll flow_limit = inf){ return min_flow_(s,t,flow_limit); }
};

// function                           : return                : description
// --------------------------------------------------------------------------------------------------------------------------------------------
// constructor()                               :                       : 
// constructor(n)                              :                       : サイズ n で初期化する
// init(int n)                                 : void                  : サイズ n で初期化する
// add_edge(int from, int to, ll cap, ll cost) : void                  : 容量が cap の from から to への辺を張る
// edge_size()                                 : int                   : 辺のサイズを返す
// get_edge(int k)                             : void                  : k 番目の辺の情報(始点, 行き先, 容量, コスト, 流量)を返す
// get_edges()                                 : vector<edge_>         : 全ての辺の情報(始点, 行き先, 容量, コスト, 流量)を返す
// min_cost(int s, int t)                      : ll                    : s から t へ目一杯流した時の最小コストを返す
// mix_cost(int s, int t, flow_limit)          : ll                    : s から t へ flow_limit まで目一杯流した時の最小コストを返す
// mix_cost_flow(int s, int t)                 : pair<ll,ll>           : s から t へまで目一杯流した時の 流量, 最小コストを返す
// mix_cost_flow(int s, int t, flow_limit)     : pair<ll,ll>           : s から t へ flow_limit まで目一杯流した時の流量, 最小コストを返す
// slope(int s, int t)                         : vector<pair<ll,ll>>   : s から t へまで目一杯流した時の流量, コストの折線グラフを返す
// slope(int s, int t, flow_limit)             : vector<pair<ll,ll>>   : s から t へ flow_limit まで目一杯流した時の流量, コストの折線グラフを返す
// --------------------------------------------------------------------------------------------------------------------------------------------


int n, m, k;

void solve(){
    cin >> k >> n >> m;
    vector<int> A(k), B(n);
    cin >> A >> B;
    MinCostFlow mcf(n+2);
    ll inf = 1e12;
    rep(i,m){
        ll u, v, d;
        cin >> u >> v >> d;
        u--; v--;
        mcf.add_edge(u,v,inf,d);
        mcf.add_edge(v,u,inf,d);
    }
    rep(i,k) mcf.add_edge(n,A[i]-1,1,0);
    rep(i,n) mcf.add_edge(i,n+1,B[i],0);
    ll f = mcf.min_cost(n,n+1);
    pt(f)
}

int main(){
    fast_io
    int t = 1;
    // cin >> t;
    rep(i,t) solve();
}

yukicoder

結果

テストケース

ソースコード