• 最大流
  • 二分图最大匹配
• 费用流
  • 二分图最佳匹配

struct Dinic {
  int n;
  struct Edge {
    int v, r;
  };
  vector<Edge> e;
  vector<vector<int>> g;

  Dinic(int n): n(n) {
    g.assign(n + 1, {});
  }

  void add_edge(int u, int v, int r) {
    g[u].push_back(e.size()), e.push_back(Edge{v, r});
    g[v].push_back(e.size()), e.push_back(Edge{u, 0});
  }

  ll dinic(int s, int t) {
    vector<int> dis(n + 1);
    auto bfs = [&]() {
      queue<int> que;
      dis.assign(n + 1, -1);
      dis[s] = 0, que.push(s);
      while (!que.empty()) {
        int u = que.front();
        que.pop();
        if (u == t) return true;
        for (int i: g[u]) if (e[i].r) {
          int v = e[i].v;
          if (dis[v] == -1) dis[v] = dis[u] + 1, que.push(v);
        }
      }
      return false;
    };
    vector<int> cur(n + 1);
    auto dfs = [&](auto&& dfs, int u, int lim) {
      if (u == t) return lim;
      int flow = 0;
      for (int &j = cur[u]; j < g[u].size(); j++) {
        int i = g[u][j], v = e[i].v, r = e[i].r;
        if (!r || dis[v] != dis[u] + 1) continue;
        int d = dfs(dfs, v, min(r, lim - flow));
        e[i].r -= d, e[i^1].r += d, flow += d;
        if (flow == lim) break;
      }
      return flow;
    };
    ll flow = 0;
    while (bfs()) {
      cur.assign(n + 1, 0);
      flow += dfs(dfs, s, INT_MAX);
    }
    return flow;
  }
};

struct Dinic {
  int n;
  struct Edge {
    int v, r, c;
  };
  vector<Edge> e;
  vector<vector<int>> g;

  Dinic(int n): n(n) {
    g.assign(n + 1, {});
  }

  void add_edge(int u, int v, int r, int c) {
    g[u].emplace_back(e.size()), e.emplace_back(Edge{v, r, c});
    g[v].emplace_back(e.size()), e.emplace_back(Edge{u, 0, -c});
  }

  pair<int, int> dinic(int s, int t) {
    vector<int> dis(n + 1);
    auto spfa = [&]() {
      queue<int> que;
      vector<bool> inq(n + 1);
      dis.assign(n + 1, INT_MAX / 2);
      dis[s] = 0, inq[s] = true, que.push(s);
      while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (int i: g[u]) if (e[i].r) {
          int v = e[i].v, c = e[i].c;
          if (dis[u] + c < dis[v]) {
            dis[v] = dis[u] + c;
            if (!inq[v]) inq[v] = true, que.push(v);
          }
        }
      }
      return dis[t] != INT_MAX / 2;
    };
    int flow = 0, cost = 0;
    vector<int> cur(n + 1);
    vector<bool> vis(n + 1);
    auto dfs = [&](auto&& dfs, int u, int lim) {
      if (u == t) return lim;
      int flow = 0;
      vis[u] = true;
      for (int &j = cur[u]; j < g[u].size(); j++) {
        int i = g[u][j], v = e[i].v, r = e[i].r, c = e[i].c;
        if (!r || vis[v] || dis[v] != dis[u] + c) continue;
        int d = dfs(dfs, v, min(r, lim - flow));
        e[i].r -= d, e[i^1].r += d, flow += d, cost += d * c;
        if (flow == lim) break;
      }
      vis[u] = false;
      return flow;
    };
    while (spfa()) {
      cur.assign(n + 1, 0);
      while (true) {
        int dlt = dfs(dfs, s, INT_MAX);
        if (!dlt) break;
        flow += dlt;
      }
    }
    return make_pair(flow, cost);
  }
};