费用流1

费用流1

---

概述

费用流，也叫作最小费用最大流，是指在普通的网络流图中，每条边的流量都有一个单价，求出一组可行解，使得在满足它是最大流的情况下，总的费用最小。
做法一般都是简单地SPFA（也就是和EK算法类似），时间复杂度比较高，所以一般规模都挺小的。 找到一条从源点到汇点的路径，使得这条路径的单价和最小。换句话说以流量的单价作为边权值跑最短路，这边推荐使用SPFA求最短路，如果有负环的话要考虑使用消圈法。

---

最大流最小费用

有n个点，接下来 m 行，每行三个整数 u,v,c,w，表示从点 u 到点 v 存在一条有向边，容量为 c，费用为 w。

#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e3+10,M=1e5+10;
int n,m,S,T;
int head[N],idx;
int q[N],d[N],cur[N];
int pre[N],incf[N];
bool st[N];
struct Edge{
    int next,to,f,w;
}edge[M];
void add(int a,int b,int c,int d)
{
    edge[idx]=(Edge){head[a],b,c,d},head[a]=idx++;
    edge[idx]=(Edge){head[b],a,0,-d},head[b]=idx++;
}
bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    memset(st,false,sizeof st);
    q[0] = S, d[S] = 0, incf[S] = inf;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = head[t]; ~i; i =edge[i].next)
        {
            int ver = edge[i].to;
            if (edge[i].f && d[ver] > d[t] + edge[i].w)
            {
                d[ver] = d[t] + edge[i].w;
                pre[ver] = i;
                incf[ver] = min(edge[i].f, incf[t]);
                if (!st[ver])
                {
                    q[tt ++ ] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
void EK(int& flow, int& cost)
{
    flow = cost = 0;
    while (spfa())
    {
        int t = incf[T];
        flow += t, cost += t * d[T];
        for (int i = T; i != S; i = edge[pre[i] ^ 1].to)
        {
            edge[pre[i]].f -= t;
            edge[pre[i]^1].f += t;
        }
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);
    memset(head, -1, sizeof head);
    while (m -- )
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
    }
    int flow, cost;
    EK(flow, cost);
    printf("%d %d\n", flow, cost);
    return 0;
}

---

最大流最大费用

没有大的变化注意一下把每次求最短路换成求最长路即可。

bool spfa()
{
    int hh=0,tt=1;
    memset(st,false,sizeof st);
    memset(d,0xcf,sizeof d);
    memset(incf,0,sizeof incf);
    q[0]=S,d[S]=0,incf[S]=inf;
    while(hh!=tt)
    {
        int t=q[hh++];
        if(hh==N)   hh=0;
        st[t]=false;
        for(int i=head[t];~i;i=edge[i].next)
        {
            int ver=edge[i].to;
            if(edge[i].f&&d[ver]<d[t]+edge[i].w)
            {
                d[ver]=d[t]+edge[i].w;
                pre[ver]=i;
                incf[ver]=min(edge[i].f,incf[t]);
                if(!st[ver])
                {
                    q[tt++]=ver;
                    if(tt==N)   tt=0;
                    st[ver]=true;
                }
            }
        }
    }
    return incf[T]>0;
}

---