最小费用流

/**
 *    author: Akvicor
 *    created: 2019-07-26 18-37-11
**/

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
#define FAST_IO 17
#else
#define FAST_IO //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define per(i, a, n) for(int i = a; i >= n; --i)
#define prec(x) fixed << setprecision(x)
#define ms(s, n) memset(s, n, sizeof(s))
#define mod(x) ((x) %= MOD)
#define all(v) (v).begin(), (v).end()
#define sz(x) ((int)(x).size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define fi first
#define se second
#define MOD(x) const int MOD = (int)x
#define MAXN(x) const int MAXN = (int)x + 10

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<LL, LL> PLL;
typedef vector<LL> VL;
typedef vector<PLL> VLL;

namespace SOL {

    const double EPS = 1e-6;
    const double PI = acos(-1.0);
    const int INF = 0x3f3f3f3f;
    const LL LINF = 0x7f7f7f7f7f7f7f7f;

/**  >------- Akvicor's Solution -------< **/

    MOD(1e9 + 7);
    MAXN(5e3);

    struct MCMF {
        struct Edge {
            int from, to, cap, flow, cost;

            Edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w) {}
        };

        MCMF(int n){
            G = vector<vector<int> > (n+10);
            inq = vector<int> (n+10);
            p = vector<int> (n+10);
            a = vector<int> (n+10);
            d = vector<int> (n+10);
        }

        vector<Edge> edges;
        vector<vector<int> > G;

        vector<int> inq;
        vector<int> p;
        vector<int> a;
        vector<int> d;

        void add_edge(int from, int to, int cap, int cost) {
            edges.push_back(Edge(from, to, cap, 0, cost));
            edges.push_back(Edge(to, from, 0, 0, -cost));
            G[from].push_back(edges.size() - 2);
            G[to].push_back(edges.size() - 1);
        }

        bool spfa(int s, int t, int &flow, long long &cost) {
            fill(inq.begin(), inq.end(), 0);
            fill(d.begin(), d.end(), 0x3f3f3f3f+10);
            d[s] = 0;
            inq[s] = 1;
            p[s] = 0;
            a[s] = 0x3f3f3f3f;
            queue<int> Q;
            Q.push(s);
            while (!Q.empty()) {
                int u = Q.front();
                Q.pop();
                inq[u] = 0;
                for (int i = 0; i < (int) G[u].size(); i++) {
                    Edge &e = edges[G[u][i]];
                    if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
                        d[e.to] = d[u] + e.cost;
                        p[e.to] = G[u][i];
                        a[e.to] = min(a[u], e.cap - e.flow);
                        if (!inq[e.to]) {
                            Q.push(e.to);
                            inq[e.to] = 1;
                        }
                    }
                }
            }
            if (d[t] >= 0x3f3f3f3f) return false;
            flow += a[t];
            cost += (long long) d[t] * (long long) a[t];
            for (int u = t; u != s; u = edges[p[u]].from) {
                edges[p[u]].flow += a[t];
                edges[p[u] ^ 1].flow -= a[t];
            }
            return true;
        }

        pair<int, long long> run(int s, int t) {
            int flow = 0;
            long long cost = 0;
            while (spfa(s, t, flow, cost));
            return {flow, cost};
        }
    };

    void solve() {
        FAST_IO;

        int n, m, s, t, c, w;
        cin >> n >> m;
        MCMF mf = MCMF(n);
        for(int i = 0; i < m; ++i){
            cin >> s >> t >> c >> w;
            mf.add_edge(s, t, c, w);
        }

        pair<int, long long> p = mf.run(1, n);
        cout << p.fi << ' ' << p.se;

    }

/**  >----------------------------------< **/

}

int main() {

#ifdef DEBUG
    int DEBUGCNT = 0;
    clock_t DEBUGstart, DEBUGfinish;
    double DEBUGduration;
    cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
    while (DEBUGCNT < 70) {
        cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
        DEBUGstart = clock();
#endif

    SOL::solve();

#ifdef DEBUG
    DEBUGfinish = clock();
        DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
        cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
        if (cin.eof()) break;
        if (!cin.good()) break;
        if (cin.fail()) break;
        if (cin.bad()) break;
        ++DEBUGCNT;
    }
    cout << ">----------------------------------<" << endl << endl;
#endif

    return 0;
}