最小费用流

  1/**
  2 *    author: Akvicor
  3 *    created: 2019-07-26 18-37-11
  4**/
  5
  6#include <bits/stdc++.h>
  7
  8using namespace std;
  9
 10#ifdef DEBUG
 11#define FAST_IO 17
 12#else
 13#define FAST_IO //ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 14#define endl '\n'
 15#endif
 16
 17#define rep(i, n) for(int i = 0; i < (n); ++i)
 18#define reep(i, n) for(int i = 0; i <= (n); ++i)
 19#define lop(i, a, n) for(int i = a; i < (n); ++i)
 20#define loop(i, a, n) for(int i = a; i <= (n); ++i)
 21#define per(i, a, n) for(int i = a; i >= n; --i)
 22#define prec(x) fixed << setprecision(x)
 23#define ms(s, n) memset(s, n, sizeof(s))
 24#define mod(x) ((x) %= MOD)
 25#define all(v) (v).begin(), (v).end()
 26#define sz(x) ((int)(x).size())
 27#define mp(x, y) make_pair(x, y)
 28#define pb(x) push_back(x)
 29#define fi first
 30#define se second
 31#define MOD(x) const int MOD = (int)x
 32#define MAXN(x) const int MAXN = (int)x + 10
 33
 34typedef long long LL;
 35typedef unsigned long long ULL;
 36typedef pair<int, int> PII;
 37typedef vector<int> VI;
 38typedef vector<PII> VII;
 39typedef pair<LL, LL> PLL;
 40typedef vector<LL> VL;
 41typedef vector<PLL> VLL;
 42
 43namespace SOL {
 44
 45    const double EPS = 1e-6;
 46    const double PI = acos(-1.0);
 47    const int INF = 0x3f3f3f3f;
 48    const LL LINF = 0x7f7f7f7f7f7f7f7f;
 49
 50/**  >------- Akvicor's Solution -------< **/
 51
 52    MOD(1e9 + 7);
 53    MAXN(5e3);
 54
 55    struct MCMF {
 56        struct Edge {
 57            int from, to, cap, flow, cost;
 58
 59            Edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w) {}
 60        };
 61
 62        MCMF(int n){
 63            G = vector<vector<int> > (n+10);
 64            inq = vector<int> (n+10);
 65            p = vector<int> (n+10);
 66            a = vector<int> (n+10);
 67            d = vector<int> (n+10);
 68        }
 69
 70        vector<Edge> edges;
 71        vector<vector<int> > G;
 72
 73        vector<int> inq;
 74        vector<int> p;
 75        vector<int> a;
 76        vector<int> d;
 77
 78        void add_edge(int from, int to, int cap, int cost) {
 79            edges.push_back(Edge(from, to, cap, 0, cost));
 80            edges.push_back(Edge(to, from, 0, 0, -cost));
 81            G[from].push_back(edges.size() - 2);
 82            G[to].push_back(edges.size() - 1);
 83        }
 84
 85        bool spfa(int s, int t, int &flow, long long &cost) {
 86            fill(inq.begin(), inq.end(), 0);
 87            fill(d.begin(), d.end(), 0x3f3f3f3f+10);
 88            d[s] = 0;
 89            inq[s] = 1;
 90            p[s] = 0;
 91            a[s] = 0x3f3f3f3f;
 92            queue<int> Q;
 93            Q.push(s);
 94            while (!Q.empty()) {
 95                int u = Q.front();
 96                Q.pop();
 97                inq[u] = 0;
 98                for (int i = 0; i < (int) G[u].size(); i++) {
 99                    Edge &e = edges[G[u][i]];
100                    if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
101                        d[e.to] = d[u] + e.cost;
102                        p[e.to] = G[u][i];
103                        a[e.to] = min(a[u], e.cap - e.flow);
104                        if (!inq[e.to]) {
105                            Q.push(e.to);
106                            inq[e.to] = 1;
107                        }
108                    }
109                }
110            }
111            if (d[t] >= 0x3f3f3f3f) return false;
112            flow += a[t];
113            cost += (long long) d[t] * (long long) a[t];
114            for (int u = t; u != s; u = edges[p[u]].from) {
115                edges[p[u]].flow += a[t];
116                edges[p[u] ^ 1].flow -= a[t];
117            }
118            return true;
119        }
120
121        pair<int, long long> run(int s, int t) {
122            int flow = 0;
123            long long cost = 0;
124            while (spfa(s, t, flow, cost));
125            return {flow, cost};
126        }
127    };
128
129    void solve() {
130        FAST_IO;
131
132        int n, m, s, t, c, w;
133        cin >> n >> m;
134        MCMF mf = MCMF(n);
135        for(int i = 0; i < m; ++i){
136            cin >> s >> t >> c >> w;
137            mf.add_edge(s, t, c, w);
138        }
139
140        pair<int, long long> p = mf.run(1, n);
141        cout << p.fi << ' ' << p.se;
142
143    }
144
145/**  >----------------------------------< **/
146
147}
148
149int main() {
150
151#ifdef DEBUG
152    int DEBUGCNT = 0;
153    clock_t DEBUGstart, DEBUGfinish;
154    double DEBUGduration;
155    cout << endl << ">------- Akvicor's Solution -------<" << endl << endl;
156    while (DEBUGCNT < 70) {
157        cout << ">---> Test: #" << DEBUGCNT << " <---<" << endl;
158        DEBUGstart = clock();
159#endif
160
161    SOL::solve();
162
163#ifdef DEBUG
164    DEBUGfinish = clock();
165        DEBUGduration = (double)(DEBUGfinish - DEBUGstart)*1000 / CLOCKS_PER_SEC;
166        cout << ">---> Test: #" << DEBUGCNT << " time: " << fixed << setprecision(4) << DEBUGduration << " ms <---<" << endl << endl;
167        if (cin.eof()) break;
168        if (!cin.good()) break;
169        if (cin.fail()) break;
170        if (cin.bad()) break;
171        ++DEBUGCNT;
172    }
173    cout << ">----------------------------------<" << endl << endl;
174#endif
175
176    return 0;
177}