最小费用最大流

最小费用最大流（Minimum Cost Maximum Flow，MCMF）。现在网络上的每条边，除了容量外，还有一个属性：单位费用。一条边上的费用等于流量×单位费用。我们知道，网络最大流往往可以用多种不同的方式达到，所以现在要求：在保持流最大的同时，找到总费用最少的一种。

https://www.luogu.com.cn/problem/P3381

只需将 EK 算法或 Dinic 算法中找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。

基于 Dinic 算法的实现:

#include<bits/stdc++.h>
//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int  long long

const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, m, tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M], dis[N], ret;
bool vis[N];

void add(int u, int v, int w, int c) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}

void addedge(int u, int v, int w, int c) { add(u, v, w, c), add(v, u, 0, -c); }

bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    queue<int> q;
    q.push(s), dis[s] = 0, vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop(), vis[u] = false;
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] > dis[u] + cost[i]) {
                dis[v] = dis[u] + cost[i];
                if (!vis[v]) q.push(v), vis[v] = true;
            }
        }
    }
    return dis[t] != INF;
}

int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    vis[u] = true;
    int ans = 0;
    for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
        int v = ter[i];
        if (!vis[v] && cap[i] && dis[v] == dis[u] + cost[i]) {
            int x = dfs(v, t, min(cap[i], flow - ans));
            if (x) ret += x * cost[i], cap[i] -= x, cap[i ^ 1] += x, ans += x;
        }
    }
    vis[u] = false;
    return ans;
}

int mcmf(int s, int t) {
    int ans = 0;
    while (spfa(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) ans += x;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif

    int s, t;
    cin >> n >> m >> s >> t;
    while (m--) {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        addedge(u, v, w, c);
    }
    int ans = mcmf(s, t);
    cout << ans << ' ' << ret;
}