Загрузка данных


#include<bits/stdc++.h>
#define pb push_back

using namespace std;
typedef long long ll;

const ll inf = 1LL << 61;
struct MCMF {
    struct Edge {
        int from, to;
        ll cap, cost;
        Edge(int _from, int _to, ll _cap, ll _cost) {
            from = _from;
            to = _to;
            cap = _cap;
            cost = _cost;
        }
    };

    int n, s, t;
    ll flow, min_cost;
    vector<vector<int>> g;
    vector<Edge> e;
    vector<ll> d, potential;
    vector<int> par;
    bool neg;

    MCMF() {}
    MCMF(int _n) { // 0-based indexing
        n = _n + 10;
        g.assign(n, vector<int>());
        neg = false;
    }

    void add_edge(int u, int v, ll cap, ll cost, bool directed = true) {
        if (cost < 0)
            neg = true;
        g[u].emplace_back((int) e.size());
        e.emplace_back(u, v, cap, cost);
        g[v].emplace_back((int) e.size());
        e.emplace_back(v, u, 0, -cost);
        if (!directed)
            add_edge(v, u, cap, cost, true);
    }

    bool dijkstra() {
        par.assign(n, -1);
        d.assign(n, inf);
        priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
        d[s] = 0;
        q.emplace(0, s);
        while (!q.empty()) {
            int from = q.top().second;
            ll nw = q.top().first;
            q.pop();
            if (nw != d[from])
                continue;
            for (int id : g[from]) {
                int to = e[id].to;
                ll cap = e[id].cap;
                ll w = e[id].cost + potential[from] - potential[to];
                if (d[from] + w < d[to] && cap > 0) {
                    d[to] = d[from] + w;
                    par[to] = id;
                    q.emplace(d[to], to);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (d[i] < inf)
                d[i] += (potential[i] - potential[s]);
        }
        for (int i = 0; i < n; i++) {
            if (d[i] < inf)
                potential[i] = d[i];
        }
        return d[t] != inf;
    }

    ll send_flow(int v, ll cur) {
        if (par[v] == -1)
            return cur;
        int id = par[v];
        int from = e[id].from;
        ll w = e[id].cost;
        ll f = send_flow(from, min(cur, e[id].cap));
        min_cost += f * w;
        e[id].cap -= f;
        e[id ^ 1].cap += f;
        return f;
    }

    // returns {maxflow, mincost}
    pair<ll, ll> solve(int _s, int _t, ll goal = inf) {
        s = _s;
        t = _t;
        flow = 0, min_cost = 0;
        potential.assign(n, 0);
        if (neg) {
            d.assign(n, inf);
            d[s] = 0;
            bool relax = true;
            for (int i = 0; i < n && relax; i++) {
                relax = false;
                for (int from = 0; from < n; from++) {
                    for (int id : g[from]) {
                        int v = e[id].to;
                        ll cap = e[id].cap, w = e[id].cost;
                        if (d[v] > d[from] + w && cap > 0) {
                            d[v] = d[from] + w;
                            relax = true;
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++)
                if (d[i] < inf)
                    potential[i] = d[i];
        }
        while (flow < goal && dijkstra())
            flow += send_flow(t, goal - flow);
        return {flow, min_cost};
    }
};


void solve() {
    int st = 0, fin = 11;
    MCMF mcmf(12);

    mcmf.add_edge(st, 1, 150, 0);
    mcmf.add_edge(st, 2, 120, 0);
    mcmf.add_edge(st, 3, 180, 0);
    mcmf.add_edge(st, 4, 150, 0);

    vector<vector<int>> costs = {
        {5, 8, 2, 6, 9, 4},
        {7, 4, 8, 1, 5, 3},
        {6, 2, 5, 9, 3, 7},
        {8, 9, 3, 4, 6, 2}
    };

    vector<int> bi = {5, 6, 7, 8, 9, 10};
    for (int i = 1; i <= 4; i++) {
        for (int j = 0; j < bi.size(); j++) {
            mcmf.add_edge(i, bi[j], inf, costs[i - 1][j]);
        }
    }

    mcmf.add_edge(5, fin, 90, 0);
    mcmf.add_edge(6, fin, 80, 0);
    mcmf.add_edge(7, fin, 110, 0);
    mcmf.add_edge(8, fin, 100, 0);
    mcmf.add_edge(9, fin, 120, 0);
    mcmf.add_edge(10, fin, 100, 0);


    auto [flow, cost] = mcmf.solve(st, fin);
    cout << flow << " " << cost << endl; // 600 1580
}


int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}