萌新刚学费用流/kk

down 了第一个点发现我输出的最小费用比答案还小，但是交到 UOJ 上第一问都是对的。

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (r); i >= (l); --i)

using namespace std;

using ll = long long;
using db = long double;
using str = string;

#define mp make_pair
#define fi first
#define se second

#define ttt template <typename T
ttt > using V = vector<T>;
ttt, size_t N > using A = array<T, N>;

#define sz(x) int((x).size())
#define all(x, l, r) &(x)[l], &(x)[r] + 1
#define pb push_back
#define eb emplace_back

#define il inline
ttt > il bool ckmin(T& x, const T& y) { return y < x ? x = y, true : false; }
ttt > il bool ckmax(T& x, const T& y) { return x < y ? x = y, true : false; }

ttt > using pq = priority_queue<T>;
ttt > using pqg = priority_queue<T, V<T>, greater<>>;

template <int N>
struct Mcmf {
  using Flow = int;
  using Cost = int;

  struct Edge {
    int v;
    Flow cap;
    Cost cost;
  };

  int n, m, s, t;
  A<bool, N> vis;
  A<Cost, N> dis, h;
  A<V<int>, N> adj;
  A<V<int>::iterator, N> cur;
  V<Edge> e;

  void init(int n_, int s_, int t_) {
    n = n_, m = 0, s = s_, t = t_;
    rep (i, 1, n) adj[i].clear();
    e.clear();
  }
  void init(int n) { init(n + 2, n + 1, n + 2); }
  void ae(int u, int v, Flow cap, Cost cost) {
    adj[u].pb(m++), adj[v].pb(m++);
    e.pb({v, cap, cost}), e.pb({u, 0, -cost});
  }
  bool dijkstra() {
    fill_n(&vis[1], n, false);
    fill_n(&dis[1], n, numeric_limits<Cost>::max()), dis[s] = 0;
    pqg<pair<Cost, int>> q;
    q.emplace(0, s);
    while (!q.empty()) {
      auto [d, u] = q.top();
      q.pop();
      if (vis[u]) continue;
      vis[u] = true;
      for (int i : adj[u]) {
        auto [v, cap, cost] = e[i];
        if (cap && ckmin(dis[v], d + cost + h[u] - h[v])) q.emplace(dis[v], v);
      }
    }
    return vis[t];
  }
  Flow dfs(int u, Flow flow) {
    if (u == t) return flow;
    vis[u] = true;
    Flow r = flow;
    for (; cur[u] < end(adj[u]); ++cur[u]) {
      int i = *cur[u];
      auto& [v, cap, cost] = e[i];
      if (cap && dis[v] == dis[u] + cost + h[u] - h[v] && !vis[v]) {
        Flow inc = dfs(v, min(r, cap));
        if (inc) {
          vis[v] = false, r -= inc, cap -= inc, e[i ^ 1].cap += inc;
          if (!r) break;
        }
      }
    }
    return flow - r;
  }
  pair<Flow, Cost> mcmf() {
    fill_n(&h[1], n, 0);
    while (true) {
      bool fl = false;
      rep (i, 0, m - 1) {
        auto [v, cap, cost] = e[i];
        if (cap) fl |= ckmin(h[v], h[e[i ^ 1].v] + cost);
      }
      if (!fl) break;
    }
    Flow flow = 0;
    Cost cost = 0;
    while (dijkstra()) {
      rep (i, 1, n) cur[i] = begin(adj[i]);
      fill_n(&vis[1], n, false);
      Flow inc = dfs(s, numeric_limits<Flow>::max());
      rep (i, 1, n) h[i] += dis[i];
      flow += inc, cost += inc * h[t];
    }
    return {flow, cost};
  }
};

constexpr int N = 205;
int n, m, s, t;
A<int, N> w;
Mcmf<N> g;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false), cin.exceptions(cin.failbit);
  cin >> n >> m >> s >> t;
  g.init(n), g.ae(t, s, 1e9, 0);
  ll sm = 0;
  rep (i, 1, m) {
    int u, v, cap, cost;
    cin >> u >> v >> cap >> cost;
    if (cost >= 0)
      g.ae(u, v, cap, cost);
    else
      sm += (ll)cap * cost, g.ae(v, u, cap, -cost), w[u] += cap, w[v] -= cap;
  }
  rep (i, 1, n)
    if (w[i] >= 0)
      g.ae(i, g.t, w[i], 0);
    else
      g.ae(g.s, i, -w[i], 0);
  auto f1 = g.mcmf();
  g.s = s, g.t = t;
  auto f2 = g.mcmf();
  cout << f2.fi << " " << sm + f1.se + f2.se << "\n";
}