费用流：

定义：

给定一个网络 \(G=(V,E)\), 每条边除了有容量限制 \(c(u,v)\) , 还有一个单位流量的费用 \(w(u,v)\)

当 \((u,v)\) 的流量 \(f(u,v)\) 时，需要花费 \(f(u,v) \times w(u,x)\)

\(w\) 也满足对称性，即 \(w(u,v)+w(v,u)=0\)

则该网络中总花费最小的最大流称为 最小费用最大流。

即在最大化 \(\sum_{(s,v)\in E}f(s,v)\) 的前提下最小化 \(\sum_{(u,v)\in E} f(u,v) \times w(u,v)\)

分析:

可以使用 \(SSP\) 算法。

\(SSP\) 算法是一个贪心的算法，它的思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。

如果图上存在单位费用为负的圈， \(SSP\) 算法无法算出，需要用消圈算法消去负环。

使用：

只需要将 \(EK\) 算法或 \(Dinic\) 算法中寻找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。

时间复杂度为 \(O(nmk)\) ，即为 \(SPFA \times\) 增广路的长度

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int inf=0x3f3f3f3f,N=5005,M=200005;
int nxt[M],ver[M],tot=1,edge[M],head[N],w[M];
int n,m,s,t;
int maxflow,mincost;
int dis[N],pre[N],cur[N],last[N],flow[N];
bool vis[N];
queue<int> q;

void add(int x,int y,int z,int f){
    ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; w[tot]=f;
    ver[++tot]=x; edge[tot]=0; nxt[tot]=head[y]; head[y]=tot; w[tot]=-f;
}

bool spfa(int s,int t){
    memset(dis,0x7f,sizeof(dis));
    memset(flow,0x7f,sizeof(flow));
    memset(vis,0,sizeof(vis));
    q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
    while(!q.empty()){
        int x=q.front(); q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i],z=edge[i],W=w[i];
            if(!z||dis[y]<=dis[x]+W) continue;//最短路算法
            dis[y]=dis[x]+W;
            pre[y]=x;//记录上一个点
            last[y]=i;//记录上一条边
            flow[y]=min(flow[x],z);
            if(!vis[y]){vis[y]=1; q.push(y);}
        }
    }
    return pre[t]!=-1;
}

void MCMF(){
    while(spfa(s,t)){
        int x=t;
        maxflow+=flow[x]; mincost+=flow[x]*dis[x];
        while(x!=s){
            edge[last[x]]-=flow[t];
            edge[last[x]^1]+=flow[t];
            x=pre[x];
        } 
    }
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1,x,y,z,f;i<=m;i++){
        scanf("%d%d%d%d",&x,&y,&z,&f); add(x,y,z,f); 
    }
    MCMF();
    cout<<maxflow<<" "<<mincost<<endl;
    system("pause");
    return 0;
}