最小费用最大流-最小费用路算法

最小费用最大流

在求最大流的过程中，对于每一条边都有一个费用，现在希望费用最小，流最大。求最大流和最小费用。

最小费用路算法

最小费用路算法的思想是：先找最小费用路，在该路径上面增流，增加到最大流。

利用邻接表建立双向边，正向边的花费为cost，反向边的花费为-cost. 在找最小费用路的时候,从源点出发，沿着可行 (E[i].cap>E[i].flow)广度搜索每个邻接点， 如果当前的边可以继续松弛，那么就更新，就是SPFA算法，并且记录一下前驱。

当找到最小费用路以后，那么就从汇点向源点找一条，最小的可增流量,沿着增广路正向增流，反向减流，最后花费的费用为： $mincost=dis[V]*d$ 累加这个过程求出来的就是最小费用，最大流就是每次累加的可增流量

可以AC:【模板】最小费用最大流 算法复杂度：$O(V^2*E)$

const int N=5000+20;
const int M=50000+20;

int top;//当前边下标
int dis[N],pre[N];//源点到点i的最小距离，pre[i]记录前驱
bool vis[N];//标记数组
int maxflow;
int first[N];//存储头结点
struct Edge
{
    int v,next;
    int cap,flow,cost;
} E[M*2];

void init()
{
    mem(first,-1);
    top=0;
    maxflow=0;
}

void add_edge(int u,int v,int c,int cost)
{
    E[top].v=v;
    E[top].cap=c;
    E[top].flow=0;
    E[top].cost=cost;
    E[top].next=first[u];
    first[u]=top++;
}
void add(int u,int v,int c,int cost)
{
    add_edge(u,v,c,cost);
    add_edge(v,u,0,-cost);
}
bool spfa(int s,int t,int n)
{
    int i,u,v;
    queue<int>q;
    mem(vis,false);
    mem(pre,-1);
    for(int i=1; i<=n; i++) dis[i]=inf;
    vis[s]=true;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        vis[u]=false;
        for(int i=first[u]; i!=-1; i=E[i].next)
        {
            v=E[i].v;
            if(E[i].cap>E[i].flow&&dis[v]>dis[u]+E[i].cost)
            {
                dis[v]=dis[u]+E[i].cost;
                pre[v]=i;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
    if(dis[t]==inf)
        return false;
    return true;
}
int MCMF(int s,int t,int n)//minCostMaxFlow
{
    int d;
    int i,mincost=0;//maxflow当前最大流量，mincost当前最小费用
    while(spfa(s,t,n))//表示找到了从s到t的最小费用路
    {
        d=inf;
        for(int i=pre[t]; i!=-1; i=pre[E[i^1].v]) //遍历反向边
            d=min(d,E[i].cap-E[i].flow);
        maxflow+=d;//更新最大流
        for(int i=pre[t]; i!=-1; i=pre[E[i^1].v]) //增广路上正向边流量+d,反向边流量-d
        {
            E[i].flow+=d;
            E[i^1].flow-=d;
        }
        mincost+=dis[t]*d;//dis[t]为该路径上单位流量费用之和
    }
    return mincost;
}
int main()
{
    int n,m,st,ed;
    int u,v,w,c;
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    init();
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d%d",&u,&v,&w,&c);
        add(u,v,w,c);
    }
    int mincost=MCMF(st,ed,n);
    printf("%d %d\n",maxflow,mincost);
    return 0;
}