网络流 最小费用最大流

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>

//#define NDEBUG
//#include <cassert>

#define DEBUG(x) cout<<(x)<<endl;
#define DEBUGA(l,r,a) for (int i=l;i<=r;++i) cout<<a[i]<<' ';cout<<endl;
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int maxn=2e5+7;
const int inf=0x3f3f3f3f;
const int mod=998244353;
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());

inline int read(){
    int x=0,w=0;char ch=0;
    while (ch<'0'||ch>'9') {w|=ch=='-';ch=getchar();}
    while (ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return w?-x:x;
}

inline void write(int x){
    if (x<0) putchar('-'),x=-x;
    if (x>9) write(x/10);
    putchar(x%10+'0');
}

struct MCMF{
    //dinic

    struct edge{
        int v, nxt, cap, cost;
        edge(){}
        edge(int v, int nxt, int cap, int cost): v(v), nxt(nxt), cap(cap), cost(cost){}
    };
    vector<edge> e;
    int cnt;
    vector<int> head, cur;

    int n, m, S, T;
    ll maxflow, mincost;
    vector<int> dis, vis;

    MCMF(int _n,int _m,int _S,int _T): n(_n), m(_m), S(_S), T(_T){
        head.assign(n+1, -1);
        vis.assign(n+1, 0);
        cnt=0;
        e.assign(m<<1, edge());
    }

    void addedge(int u, int v, int w, int c){
        e[cnt] = {v, head[u], w, c};
        head[u] = cnt++;
        e[cnt] = {u, head[v], 0, -c};
        head[v] = cnt++;
    }

    bool spfa(){
        dis.assign(n+1, inf);
        queue<int> q;
        dis[S] = 0;
        vis[S] = 1;
        q.push(S);
        while (!q.empty()){
            int u = q.front(); q.pop();
            vis[u] = 0;
            for (int i=head[u]; ~i; i=e[i].nxt){
                int v = e[i].v;
                if (e[i].cap && dis[v] > dis[u]+e[i].cost){
                    dis[v] = dis[u]+e[i].cost;
                    if (!vis[v]) q.push(v), vis[v] = 1;
                }
            }
        }
        return dis[T]!=inf;
    }

    int dfs(int u, int flow){
        if (u==T) return flow;
        int res = 0;
        vis[u]=1;
        for (int& i = cur[u]; ~i && res<flow; i = e[i].nxt){
            int v = e[i].v;
            if (!vis[v] && e[i].cap && dis[v]==dis[u]+e[i].cost){
                int d=dfs(v, min(e[i].cap, flow-res));
                if (d) {
                    mincost += d * e[i].cost;
                    e[i].cap -= d;
                    e[i^1].cap += d;
                    res += d;
                }
            }
        }
        vis[u]=0;
        return res;
    }

    pll mcmf(){
        maxflow = mincost = 0;
        while (spfa()){
            cur.assign(head.begin(), head.end());
            int x;
            while (x = dfs(S,inf)) maxflow += x;
        }
        return {maxflow, mincost};
    }
};

void solve(){
    int n,m,s,t;
    cin>>n>>m>>s>>t;
    MCMF mf(n+1, m<<1, s, t);
    int u,v,w,c;
    while (m--){
        cin>>u>>v>>w>>c;
        mf.addedge(u, v, w, c);
    }
    auto [maxflow, mincost] = mf.mcmf();
    cout<<maxflow<<" "<<mincost<<endl;
}


int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
//    cin>>T;
    while (T--) solve();

    return 0;
}