P3381

Aryper · 2021-10-28 08:21:03 · 个人记录

【模板】最小费用最大流

其实就是在 EK 的基础上把 BFS 换成 SPFA 即可。边权就是单位流量费用，每次 SPFA 求该值的最短路，然后其他都差不多。

时间复杂度 O(nm^2)。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll inf=(1ll<<31),N=5e3,M=5e4;

ll n,m,s,t,tot,u,v,c,w,maxflow,mincost;

ll ver[M*2+5],nxt[M*2+5],head[N+5],edge[M*2+5],wt[M*2+5];
ll incf[N+5],dist[N+5],pre[N+5];

bool vis[N+5];

bool spfa() {
    queue<ll> q;
    memset(vis,0,sizeof(vis));
    for(ll i=1;i<=n;i++) dist[i]=inf;
    q.push(s);dist[s]=0;vis[s]=1;
    incf[s]=inf;
    while(!q.empty()) {
        ll h=q.front();q.pop();vis[h]=0;
        for(ll i=head[h];i;i=nxt[i]) {
            if(!edge[i]) continue;
            if(dist[ver[i]]>dist[h]+wt[i]) {
                dist[ver[i]]=dist[h]+wt[i];
                incf[ver[i]]=min(incf[h],edge[i]);
                pre[ver[i]]=i;
                if(!vis[ver[i]]) {
                    vis[ver[i]]=1;q.push(ver[i]);
                }
            }
        }
    }
    if(dist[t]==inf) return 0;
    return 1;
}

void update() {
    ll x=t;
    while(x!=s) {
        ll i=pre[x];
        edge[i]-=incf[t];
        edge[i^1]+=incf[t];
        x=ver[i^1];
    }
    maxflow+=incf[t];
    mincost+=dist[t]*incf[t];
}

void add(ll u,ll v,ll c,ll w) {
    ver[++tot]=v;edge[tot]=c;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
    ver[++tot]=u;edge[tot]=0;wt[tot]=-w;
    nxt[tot]=head[v];head[v]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();s=read();t=read();

    tot=1;
    for(ll i=1;i<=m;i++) {
        u=read();v=read();c=read();w=read();
        add(u,v,c,w);
    }

    while(spfa()) update();

    write(maxflow);putchar(' ');
    write(mincost);

    return 0;
}