P3381 【模板】最小费用最大流

link

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cstring>
#include <queue>
# define LL long long
using namespace std;

const int INF=0x7fffffff;
const int maxn=5000+10;
const int maxm=50000+10;
int N,M,S,T;
int res1;
int res2;
int head[maxn];
int en;
struct Edge{
    int to;
    int next;
    int c;
    int fi;
}e[maxm<<1];

int dis[maxn];
int preedge[maxn];
int minflow[maxn];
int inque[maxn];

void addEdge(int from, int to, int capa, int f){
    e[en].next=head[from];
    e[en].to=to;
    e[en].c=capa;
    e[en].fi=f;
    head[from]=en;
    ++en;
}

void add(int from, int to, int capa, int f){
    addEdge(from,to,capa,f);
    addEdge(to,from,0,-f);
}

void spfa(){
    memset(preedge,-1,sizeof(preedge));
    memset(minflow,0,sizeof(minflow));
    memset(dis,0x3f, sizeof(dis));
    memset(inque,0,sizeof(inque));

    queue<int> q;
    q.push(S);
    dis[S]=0;
    minflow[S]=INF;
    inque[S]=1;
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        inque[cur]=0;
        for(int i=head[cur];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(e[i].c>0 && dis[v]>dis[cur]+e[i].fi){
                dis[v]=dis[cur]+e[i].fi;
                preedge[v]=i;
                minflow[v]=min(minflow[cur],e[i].c);
                if(inque[v]==0){
                    q.push(v);
                    inque[v]=1;
                }
            }
        }
    }
}

void EK(){
    while(true){
        spfa();
        if(preedge[T]==-1) break;
        res1+=minflow[T];
        res2+=minflow[T]*dis[T];
        int v=T;
        while(true){
            int edge=preedge[v];
            int u=e[edge^1].to;
            e[edge].c-=minflow[T];
            e[edge^1].c+=minflow[T];
            if(u==S) break;
            v=u;
        }
    }
}

int main(){
    memset(head,-1,sizeof(head));
    scanf("%d %d %d %d", &N, &M, &S, &T);
    while(M--){
        int u,v;
        int c,f;
        scanf("%d %d %d %d", &u, &v, &c, &f);
        add(u,v,c,f);
    }
    EK();
    printf("%d %d", res1, res2);
    return 0;
}