Cod sursă (job #821818)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll INF = (1LL<<60);

// Edge structure for MCMF
struct Edge {
    int to, rev;
    ll cap, cost;
};

struct MCMF {
    int N;
    vector<vector<Edge>> g;
    vector<ll> dist, potential;
    vector<int> pvnode, pvedge;

    MCMF(int n): N(n), g(n), dist(n), potential(n), pvnode(n), pvedge(n) {}

    // add edge u->v with capacity c and cost w
    void addEdge(int u, int v, ll c, ll w) {
        g[u].push_back({v, (int)g[v].size(), c, w});
        g[v].push_back({u, (int)g[u].size()-1, 0, -w});
    }

    // compute min-cost max-flow from s to t, up to maxf flow
    // returns pair{flow, cost}
    pair<ll,ll> minCostMaxFlow(int s, int t, ll maxf) {
        ll flow = 0, flowCost = 0;
        // initialize potentials with Bellman-Ford (or 0)
        fill(potential.begin(), potential.end(), 0);
        // successive augment
        while (flow < maxf) {
            // Dijkstra on reduced costs
            priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            pq.emplace(0, s);

            while (!pq.empty()) {
                auto [cd, u] = pq.top(); pq.pop();
                if (cd > dist[u]) continue;
                for (int ei = 0; ei < (int)g[u].size(); ++ei) {
                    auto &e = g[u][ei];
                    if (e.cap <= 0) continue;
                    ll nd = cd + e.cost + potential[u] - potential[e.to];
                    if (nd < dist[e.to]) {
                        dist[e.to] = nd;
                        pvnode[e.to] = u;
                        pvedge[e.to] = ei;
                        pq.emplace(nd, e.to);
                    }
                }
            }
            if (dist[t] == INF) break;

            // update potentials
            for (int i = 0; i < N; ++i) {
                if (dist[i] < INF) potential[i] += dist[i];
            }

            // find how much we can send
            ll addf = maxf - flow;
            int v = t;
            while (v != s) {
                auto &e = g[pvnode[v]][pvedge[v]];
                addf = min(addf, e.cap);
                v = pvnode[v];
            }
            // apply flow
            v = t;
            while (v != s) {
                auto &e = g[pvnode[v]][pvedge[v]];
                e.cap -= addf;
                g[v][e.rev].cap += addf;
                flowCost += addf * e.cost;
                v = pvnode[v];
            }
            flow += addf;
        }
        return {flow, flowCost};
    }
};

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

    // input
    freopen("stampile.in","r",stdin);
    freopen("stampile.out","w",stdout);

    int N, M;
    cin >> N >> M;
    vector<ll> S(N+1);
    for (int i = 1; i <= N; ++i) cin >> S[i];

    struct Office { int A, B; ll V; };
    vector<Office> office(M);
    for (int j = 0; j < M; ++j) {
        cin >> office[j].A >> office[j].B >> office[j].V;
    }

    // Build network with lower bounds:
    // Nodes 0..N. We'll send a circulation on this ring.
    // Edge (i-1)->i with lower=S[i], cap=INF, cost=0.
    // Edge (A-1)->B with lower=0, cap=V_j, cost=1.
    // Then standard lower-bound elimination + super-source/sink.

    int V = N+1;
    vector<ll> demand(V, 0);

    auto addDemand = [&](int u, int v, ll low){
        demand[u] -= low;
        demand[v] += low;
    };

    // We'll build MCMF on a graph size = V + 2 (for s,t)
    int s = V, t = V+1;
    MCMF mcmf(V+2);

    // 1) chain edges with lower bounds
    for (int i = 1; i <= N; ++i) {
        ll low = S[i];
        // original cap = INF, cost=0
        // after elimination: cap' = INF - low = INF
        addDemand(i-1, i, low);
        mcmf.addEdge(i-1, i, LLONG_MAX/4, 0);
    }

    // 2) office edges
    for (int j = 0; j < M; ++j) {
        int u = office[j].A - 1;
        int v2 = office[j].B;
        ll cap = office[j].V;
        // lower=0 ? no demand change
        mcmf.addEdge(u, v2, cap, 1);
    }

    // 3) connect super-source/sink for demands
    ll totalDemand = 0;
    for (int i = 0; i < V; ++i) {
        if (demand[i] > 0) {
            mcmf.addEdge(s, i, demand[i], 0);
            totalDemand += demand[i];
        } else if (demand[i] < 0) {
            mcmf.addEdge(i, t, -demand[i], 0);
        }
    }
    // 4) allow circulation by connecting t->s with infinite cap
    mcmf.addEdge(V-1, 0, LLONG_MAX/4, 0);  // link node N back to 0
    mcmf.addEdge(t, s, LLONG_MAX/4, 0);

    // 5) find min-cost max-flow from s to t
    auto [flow, cost] = mcmf.minCostMaxFlow(s, t, totalDemand);

    if (flow < totalDemand) {
        cout << -1 << "\n";
    } else {
        // cost so far counts also any cost on t->s edge if used (0), so it's just visits
        cout << cost << "\n";
    }

    return 0;
}