最小费用流板子

洛谷3381

最小费就是拿spfa对费用跑最短路。先跑出一条线，然后在更新这条路，最后直到走不到汇点就退出，有点像不断bfs找最大流就是ek算法加spfa，注意一点就是，反向边在建立的时候花费为负的花费，因为如果走反向边就代表反悔 ，就要把扣去的钱补回来就是加上负值。

直接看代码吧。。。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn=5e3+1;
const int maxm=5e4+1;
const int inf=0x3f3f3f3f;
struct node {
    int u,v,dis,flow,next;
}nodes[maxm<<1];
int cnt,head[maxn],s,t,n,m,maxflow,mincost;
bool vis[maxn];
int pre[maxn],dis[maxn],edge[maxn],Flow[maxn];
void add_node(int u,int v,int dis,int flow) {
    nodes[cnt]={u,v,dis,flow,head[u]};
    head[u]=cnt++;
}
bool spfa(int s,int t) {
    queue<int>que;
    memset(dis,inf,sizeof dis);
    memset(vis,false,sizeof vis);
    memset(Flow,inf,sizeof Flow);
    que.push(s);
    vis[s]=true;
    pre[t]=-1;
    dis[s]=0;
    while(!que.empty()) {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=head[u];~i;i=nodes[i].next) {
            int v=nodes[i].v;
            if(nodes[i].flow>0 && dis[v]>dis[u]+nodes[i].dis) {
                if(!vis[v]) {
                    que.push(v);
                    vis[v]=true;
                }
                pre[v]=u;
                dis[v]=dis[u]+nodes[i].dis;
                edge[v]=i;
                Flow[v]=min(Flow[u],nodes[i].flow);
            }
        }
    }
    return pre[t]!=-1;
}
void mcmf() {
    while(spfa(s,t)) {
        int u=t;
        maxflow+=Flow[t];
        mincost+=Flow[t]*dis[t];
        while(s!=u) {
            nodes[edge[u]].flow-=Flow[t];
            nodes[edge[u]^1].flow+=Flow[t];
            u=pre[u];
        }
    }
}
int main() {
    memset(head,-1,sizeof head);
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++) {
        int u,v,dis,flow;
        scanf("%d%d%d%d",&u,&v,&flow,&dis);
        add_node(u,v,dis,flow);
        add_node(v,u,-dis,0);
    }
    mcmf();
    printf("%d %d",maxflow,mincost);
    return 0;
}

另加上一段最大流的部分板子

bool bfs(int s,int t) {
    for(int i=0;i<=501+n+1;i++) {
        d[i]=-1;
        cur[i]=head[i];
    }
    queue<int>que;
    que.push(s);
    d[s]=0;
    while(!que.empty()) {
        int u=que.front();
        que.pop();
        if(u==t) break;
        for(int i=head[u];i!=-1;i=nodes[i].next) {
            int v=nodes[i].v;
            if(d[v]==-1 && nodes[i].val>0) {
                d[v]=d[u]+1;
                que.push(v);
            }
        }
    }
    return d[t]!=-1;
}   
int dfs(int u,int t,int flow) {
    int nowflow=0;
    if(u==t) return flow;
    for(int i=cur[u];i!=-1;i=nodes[i].next) {
        cur[u]=i;
        int v=nodes[i].v;
        if(d[v]==d[u]+1 && nodes[i].val>0) {
            if(int k=dfs(v,t,min(flow-nowflow,nodes[i].val))) {
                nodes[i].val-=k;
                nodes[i^1].val+=k;
                nowflow+=k;
                if(flow==nowflow) break;
            }
        }
        
    }
    return nowflow;
}
int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t)) {
        int dis=dfs(s,t,inf);
        ans+=dis;
    }
    return ans;
}

优化方法根据这篇博客来的