Posted on 2019-08-27

|

Post modified: 2019-08-27

| In algorithm

| Visitors:

最小费用最大流

从上次讲最大流已经过了一段时间了，这次我们讲一讲最大流的另一种特殊情况，费用流，其全名应该是最小费用最大流。这个在算法竞赛中十分常用，因为只要牵扯到需要拆点和拆边的情况下，我们都需要用费用流，而这种操作实在是不能在普通了。

在这里，问题相比最大流要稍微复杂一些，给定我们一个图GG，和图中一些边EE,但是其中每条边有两种属性：

• 该条边的最大流量
• 该条边每通过一个流量，所需要的花费

之后给定源点和汇点。问我们怎样用最小费用得到最大流量。

其实这个问题也是一个很实际的问题，一个图，我们得到最大流的方式有很多，但是我们怎么得到最优的最大流方案？

这个时候，就轮到我们的EK算法出场了，我们只需要每次贪心的遵循每次走花费最少的路径从源点到汇点就好了，正确性是显而易见的。在我们找到话费最少的路径之后，我们也去得到限制的流量最小的瓶颈，之后构造反向边得到残差网络。计算花费的时候，只需要统计整条路径的花费乘上流量就好了。整个过程其实是非常简单的，写起来比dinic要轻松多了。

但是本文的目的并不是介绍这个算法，而是介绍一些常用的技巧。

拆点的意思很简单，就是我们限制节点经过的流量大小，换句话说，我们不仅有边有性质，我们的点也有性质，主要分为两种

• 点有流量限制
• 点有点权限制

这个时候，我们只需要把点一分为二。同时中间根据需要，加上节点的边就好了。

• 经过该节点，每个单位流量，需要花费ww。这个时候我们把点拆成两个部分，加一条边，其中流量无限大，花费位ww就好了
• 经过该节点有流量限制FF，这个时候我们只需要，把点拆成两个部分，同时加上一条边，流量为FF，费用为00就好了。

超级源点，超级汇点

有时候我们会遇到有多个源点，多个汇点的问题。

我们通常的做法，就是自己增加两个节点，作为超级源点/汇点，超级源点/汇点连接所有源点/汇点，其中的流量和边权需要特殊情况特殊考虑。

拆边的时候，其实是很少见的，一般情况下，是由于边的代价公式不同，我们需要根据不同的流量建边，比如说花费是cost∗flow2cost∗flow2。

有时候我们遇到一些题目，它求的是，所有边权的乘积作为花费。这个时候我们可以把边权取log，之后再正常计算就好了。

最大费用最大流

我们在做最小费用最大流的时候，只需要把边权先取反就好了。最后结果再取反。具体可以看下面的这个例题

一道具体例题

有一个矩阵AA，形状为n∗mn∗m ，表示有nn个人和mm个项目。AijAij表示编号为ii的人完成项目jj可以得到的回报为AijAij。同时每个任务只能完成一次，且每个人只能完成一个项目，问怎么安排，得到的结果最大？

这是一个十分明显的最大费用最大流的题目，同时我们可以根据超级源点和汇点的写法，选择拆或者不拆点。

下面给出解法

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int INF=1e9;
struct Edge{
    int from,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
};
struct MCMF{
    int n,m;
    static const int maxn=4105;
    vector<Edge> edges;
    vector<int> G[maxn];
    int inq[maxn]; //是否在队列中
    int d[maxn]; //bellman
    int p[maxn];  //上一条狐的编号
    int a[maxn]; //可该进量

void init(int n){
        this->n=n;
        for(int i=0;i<n;i++)G[i].clear();  //注意编号
        edges.clear();
    }
    void addEdge(int from,int to,int cap,int cost){
        edges.push_back(Edge(from,to,cap,0,cost));
        edges.push_back(Edge(to,from,0,0,-cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BellmanFord(int s,int t,int &flow,long long &cost){
        for(int i=0;i<n;i++)d[i]=INF; //注意编号
        memset(inq,0,sizeof inq);
        d[s]=0;inq[s]=1;p[s]=-1;a[s]=INF;
        queue<int> Q;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0;i<G[u].size();i++){
                Edge &e=edges[G[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(d[t]==INF)return false;
        flow+=a[t];
        cost+=(LL)d[t]*a[t];
        for(int u=t;u!=s;u=edges[p[u]].from){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    //需要保证初始网络中没有负权圈
    int MincostMaxflow(int s,int t,long long& cost){
        int flow=0;
        cost=0;
        while(BellmanFord(s,t,flow,cost));
        return flow;
    }
}MF;

int main(void){
    int i,j,n,m,c,S,T,f;
    long long cost;
    scanf("%d %d",&n,&m);
    MF.init(2+(n+m)*2+10);
    S=2*(n+m)+1;
    T=2*(n+m)+2;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            scanf("%d",&c);
            MF.addEdge(n+i,2*n+j,1,-c);
        }
    }
    for(i=1;i<=n;i++){
        MF.addEdge(S,i,1,0);
        MF.addEdge(i,n+i,1,0);
    }
    for(i=1;i<=m;i++){
        MF.addEdge(2*n+i,2*n+m+i,1,0);
        MF.addEdge(2*n+m+i,T,1,0);
    }
    f=MF.MincostMaxflow(S,T,cost);
    printf("%lld",-cost);
}
/*
3 3
1 3 3
2 2 2
3 2 1
 */