結果

問題 No.2604 Initial Motion
ユーザー srjywrdnprkt
提出日時 2024-01-14 23:47:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 763 ms / 3,000 ms
コード長 3,225 bytes
コンパイル時間 2,436 ms
コンパイル使用メモリ 214,532 KB
最終ジャッジ日時 2025-02-18 20:07:21
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>;

struct edge{
    int to; ll cap, cost; int rev;
};

struct MinCostFlow{

    private:
        static const ll INF=9e18;
        vector<ll> dist, h;
        vector<int> prevv, preve;
        vector<pair<int, int>> idx;

        void dijkstra(int s){
            int from, c;
            pq<pair<ll, int>> que;

            for (int i=0; i<N; i++) dist[i] = INF;
            que.push({0, s});
            dist[s] = 0;
            while(!que.empty()){
                tie(c, from) = que.top(); que.pop();
                if (dist[from] < c) continue;
                for (int i=0; i<E[from].size(); i++){
                    edge &e = E[from][i];
                    if (e.cap > 0 && dist[e.to] > dist[from]+e.cost+h[from]-h[e.to]){
                        dist[e.to] = dist[from]+e.cost+h[from]-h[e.to];
                        prevv[e.to] = from; preve[e.to] = i;
                        que.push({dist[e.to], e.to});
                    }
                }
            }
        }

    public:
        int N, M=0;
        vector<vector<edge>> E;

        MinCostFlow(int n) : N(n) {
            E.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){
            M++;
            idx.push_back({from, (int)E[from].size()});
            E[from].push_back({to, cap, cost, (int)E[to].size()});
            E[to].push_back({from, 0, -cost, (int)E[from].size()-1});
        }

        ll solve(int s, int t, ll f){
            ll res = 0, flow;
            fill(h.begin(), h.end(), 0);
            while(f){
                dijkstra(s);
                if (dist[t] == INF) return -1; //no solution

                for (int i=0; i<N; i++) h[i] += dist[i];
                flow = f;
                for (int i=t; i!=s; i=prevv[i]) flow = min(flow, E[prevv[i]][preve[i]].cap);
                f -= flow;
                res += flow*h[t];
                for (int i=t; i!=s; i=prevv[i]){
                    edge &e = E[prevv[i]][preve[i]];
                    e.cap -= flow;
                    E[i][e.rev].cap += flow;
                }
            }
            return res;
        }

        //i番目の辺の(from, to, flow)を求める。
        tuple<int, int, ll> get_flow(int i){
            assert (i < M);
            edge &e = E[idx[i].first][idx[i].second];
            return {idx[i].first, e.to, E[e.to][e.rev].cap};
        }
};

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    ll K, N, M, u, v, d, s, t;
    cin >> K >> N >> M;
    MinCostFlow mcf(N+2);
    s = 0;
    t = N+1;
    vector<ll> A(N+1), B(N+1);
    for (int i=1; i<=K; i++){
        cin >> u;
        A[u]++;
    }
    for (int i=1; i<=N; i++) cin >> B[i];
    for (int i=1; i<=N; i++) mcf.add_edge(s, i, A[i], 0);
    for (int i=1; i<=N; i++) mcf.add_edge(i, t, B[i], 0);

    for (int i=0; i<M; i++){
        cin >> u >> v >> d;
        mcf.add_edge(u, v, K, d);
        mcf.add_edge(v, u, K, d);
    }

    cout << mcf.solve(s, t, K) << endl;

    return 0;
}
0