费用流模板

费用流模板

#include
using namespace std;
const int N = 5010, M = 1e5 + 20;
const int INF = 1e8;
int n, m, S, T;

int e[M], f[M], w[M], ne[M], h[M], idx;
void add(int u, int v, int c, int d){
    e[idx] = v, f[idx] = c, w[idx] = d, ne[idx] = h[u], h[u] = idx++;
    e[idx] = u, f[idx] = 0, w[idx] = -d, ne[idx] = h[v], h[v] = idx++;
}

int q[N], d[N], pre[N], incf[N];
bool st[N];
bool spfa(){
    int hh = 0, tt = 1;
    memset(incf, 0, sizeof incf);
    memset(d, 0x3f, sizeof d);
    q[0] = S, st[S] = true, d[S] = 0, incf[S] = INF;
    while(hh != tt){
        int u = q[hh++];
        if(hh == N) hh = 0;
        st[u] = false;
        
        for(int i = h[u]; ~i; i = ne[i]){
            int v = e[i];
            if(f[i] && d[v] > d[u] + w[i]){
                d[v] = d[u] + w[i];
                pre[v] = i;
                incf[v] = min(incf[u], f[i]);
                if(!st[v]){
                    q[tt++] = v;
                    st[v] = true;
                    if(tt == N) tt = 0;
                }
            }
        }
    }
    return incf[T] > 0;
}

void EK(int &flow, int &cost){
    flow = 0, cost = 0;
    while(spfa()){
        int t = incf[T];
        flow += t, cost += t * d[T];
        for(int i = T; i != S; i = e[pre[i] ^ 1]){
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
        }
    }
}

int main(){
    memset(h, -1, sizeof h);
    scanf("%d%d%d%d", &n, &m, &S, &T);
    for(int i = 1; i <= m; i++){
        int u, v, c, d;
        scanf("%d%d%d%d", &u, &v, &c, &d);
        add(u, v, c, d);
    }
    int flow, cost;
    EK(flow, cost);
    printf("%d %d\n", flow, cost);
    return 0;
}