费用流模板--EK

费用流

#include <bits/stdc++.h>
using namespace std;
const int N=5005,M=1e6+5,inf=1e9;

int h[N],ne[M],e[M],w[M],c[M],tot=1;
void add(int from,int to,int w1,int w2,int ci) {
    e[++tot]=to;  w[tot]=w1;  c[tot]=ci;  ne[tot]=h[from];  h[from]=tot;
    e[++tot]=from;w[tot]=w2;  c[tot]=-ci; ne[tot]=h[to];    h[to]=tot;
}

int S,T;
bool st[N];
int dis[N],pre[N],flow[N];
bool spfa() {
    memset(dis,0x3f,sizeof(dis));
    memset(flow,0,sizeof(flow));
    queue<int>q;
    q.push(S);
    flow[S]=inf;
    dis[S]=0;
    st[S]=1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        st[now]=0;
        for(int i=h[now];i;i=ne[i]) {
            int to=e[i];
            if(w[i]>0&&dis[to]>dis[now]+c[i]) {
                dis[to]=dis[now]+c[i];
                pre[to]=i;
                flow[to]=min(w[i],flow[now]);
                if(st[to]==0)q.push(to),q.push(to);
            }
        }
    }
    return flow[T];
}

void EK() {
    int ans1=0,ans2=0;
    while(spfa()) {
        int tmp=flow[T];
        ans1+=tmp,ans2+=tmp*dis[T];
        for(int i=T;i!=S;i=e[pre[i]^1]) {
            w[pre[i]]-=tmp;
            w[pre[i]^1]+=tmp;
        }
    }
    cout<<ans1<<' '<<ans2<<endl;
}

int main() {
    int n,m;
    cin>>n>>m>>S>>T;
    while(m--) {
        int x,y,wi,ci;
        cin>>x>>y>>wi>>ci;
        add(x,y,wi,0,ci);
    }
    EK();
    return 0;
}