最小费用最大流

此页面存在相关页面。关于网络流基础，请参见「网络最大流」。

最小费用最大流（Min Cost Max Flow，MCMF，也称费用流）问题，是指在网络流图中，对于每条边在原有的基础上再增加一个限制——单位流量的费用……

一 概念

最小费用最大流（Min Cost Max Flow，MCMF，也称费用流）问题，是指在网络流图中，对于每条边在原有的基础上再增加一个限制——单位流量的费用，并且在保证流最大的情况下使得产生的费用最小。

那么在费用流问题中，一条边就可以被描述成$e=(u,v,cap,cost,flow)$，$(u,v)$是边的起点和终点，$cap$是容量限制，$cost$是单位流量所产生的费用，$flow$是当前流量。
之所以强调“单位流量“，是因为这条边总产生的费用为$flow\times cost$。

网络的最大流显然是一定的，但是最小割可能会有多个。每个割的单位流量费用不同，于是才有了费用流问题。注意：费用流是在保证流最大的前提下，使得总产生的费用最小。

---

二 解决

1 思路

网络的最大流可能是由多条增广路径共同组成。如下图，增广路$s \to 1 \to 4 \to t$和$s \to 2 \to 3 \to t$共同组成了网络的最大流。

那么先分析一条增广路的费用。
设该费用为$p$，该增广路经过边$e_1,e_2,…,e_m$，每条边的单位流量费用分别是$c_1,c_2,…,c_m$，且该路上当前流量为$a$，那么可以得出下面的式子：

$$ p = ac_1 + ac_2 + … + ac_m = a(c_1+c_2+…+c_m) $$
也就是：
$$ p = a \times \sum\limits_{i=1}^m c_i $$

如果能保证$p$最小且该增广路在最大流中，那么$a$一定是个定值，且等于路上的最小割。
要保证$p$最小，就是要让后面的$\sum$最小，它表示该增广路上各条边的单位费用之和。

那么我们能想到什么？最短路
把$cost$这一元看作边的边权，那么这个$\sum\limits_{i=1}^m c_i$就表示路上的边权之和。我们要求出最小的$\sum$，就是在求图上的最短路。

那么就有了贪心的思路：每次找出图上$s\to t$的最短路并把它增广，那么这条路就“断”了，然后再找最短路，直到无法增广，此时网络达到最大流，且产生的费用最小。

2 代码

利用spfa找最短路，每次进行单路增广，并模拟dinic中dfs增广的退栈过程来实现数据的更新（这需要记录搜索时进入每个节点的边时哪一条边）。

注意，因为反向边是反悔机制，用来抵消正向边的影响，所以反向边的单位流量费用应该是对应正向边的相反数。

const int CP=5e3+3;
const int CE=1e5+1e2;

const int INF=0x3f3f3f2f;

//快读
int read(){ 
    int s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=((s<<1)+(s<<3))+c-'0';
    return s*ne;
}

//边表
class fs{ 
  public:
      int from,to,nxt,cap,cost,flow;
      void init(int r,int t,int n,int c,int s,int f)
    {from=r; to=t; nxt=n; cap=c; cost=s; flow=f;}
}E[CE];
int hd[CP],ecnt=1;
void _add(int x,int y,int c,int s){
    E[++ecnt].init(x,y,hd[x],c,s,0);
    hd[x]=ecnt;
}
void add(int x,int y,int c,int s){
    _add(x,y,c,s);
    _add(y,x,0,-s); //反向边
}

//v define
int n,m,s,t;

//mcmf
int mincost=0,maxflow=0;
int dist[CP]; //dist : 单源最短路
bool ins[CP]; //ins[i] : i 是否在队列内
int prv[CP]; //prv[i] : 当前最短路中进入点 i 的边 
int rst[CP]; //rst[i] : s->i路上的最小割

bool Augment(int _s,int _t) //spfa
{
    memset(ins,false,sizeof(ins));
    memset(dist,0x3f,sizeof(dist));
    memset(rst,0x3f,sizeof(rst));
    
    queue<int>Q;
    Q.push(_s); dist[_s]=0; ins[_s]=true;
    
    while(!Q.empty())
    {
        int u=Q.front(); Q.pop();
        ins[u] = false;
        for(int k=hd[u]; k; k=E[k].nxt){
            fs e=E[k];
            if(e.cap-e.flow > 0 && dist[e.to] > dist[u]+e.cost)
            {
                dist[e.to] = dist[u]+e.cost; //松弛，边权为cost
                prv[e.to] = k; //记录入边
                rst[e.to] = min(rst[u], e.cap-e.flow); //递推
                if(!ins[e.to]){
                    Q.push(e.to); ins[e.to] = true;
                }
            }
        }
    }
    
    return dist[_t]<INF; //没到达 _t ，则dist[_t]=INF
}
void update(int _s,int _t){ //更新（模拟退栈）
    int pos=_t; //从终点开始
    while(pos != _s){ //直到起点
        E[prv[pos]].flow += rst[_t]; //正向
        E[prv[pos]^1].flow -= rst[_t]; //反向
        pos = E[prv[pos]].from; //前往上一个节点
    }
}
void mcmf(int _s,int _t){ //主调用函数
    while(Augment(_s,_t)){
        maxflow += rst[_t];
        mincost += dist[_t]*rst[_t]; //单位费用 * 流量
        update(_s,_t); //更新
    }
}

---

三 网络流建模

1 点容量问题

拆点建模一般应用在点存在容量限制的网络流问题中，因此也可以用来求解图上的最小割点集（此时点的容量均为$1$，详见「题解」奶牛的电信）。

把图上的每个非源非汇点$i$拆成$i,i+n$两个点（$n$是总点数），其中点$i$连接原图中该点的入边，点$i+n$连接原图中该点的出边，这样$i\to i+n$这条边就能代表原图中的点$i$，对这条边设置容量限制，实际就是对该点设置容量限制。

如下图：

2 点权均衡问题

原题：负载平衡问题

给定一张由$n$个点组成的环，每个点$i$有一个点权$x_i$，点权可以在相邻节点间转移。记$ \overline x = \sum\limits_{i=1}^n x_i \div n$，求最少的转移量，使得每个$x_i$都等于$\overline x$。

可以把仓库分成两类：

1. $x_i > \overline x$ 的仓库$i$，记为图$L$。
2. $x_i < \overline x$ 的仓库$i$，记为图$R$。

$x_i = \overline x$的仓库不会影响答案，所以放在哪一类里面都行。

很明显，$L$中节点的点权需要转移到$R$中节点去。
把这个点权变成边权，那么新建总源$s$和总汇$t$，连边$s\to L$，$L \rightleftarrows R$与$R\to t$。具体方法如下：

1. $s\to L$边上的流量限制为$L$中节点点权超出$\overline x$的部分，即$x_i - \overline x$，转移费用为$0$。
2. $R\to t$边上的流量限制为$R$中节点点权不足$\overline x$的部分，即$\overline x- x_i$，转移费用为$0$。
3. 图上所有相邻节点互相连双向边，边上没有流量限制，因为可以无限转移。不过转移的费用就是$1$。

这样，当增广一条路时，$s\to L$的边流量增大，使得$L$中节点点权变小；$R\to t$的边流量也增大，使得$R$中节点点权变大。
其实上意味着$L,R$中点的点权会更接近于平均值$\overline x$。当网络流达到最大时，也就是说所有不等于平均值的点权都已经被增广到平均值大小，也就达到了负载平衡。

那么跑费用流，输出最小费用。

---

四 二分图匹配问题

1 最大基数匹配

二分图的不带权最大匹配问题也称最大基数匹配问题。基础部分详见：二分图基础。

新建总源$s$，总汇$t$。设二分图的左图为$L$，右图为$R$，则将$s$向$L$中的所有节点连边，$R$中的所有节点向$t$连边，并将二分图中原有的无向边转化成$L\to R$的有向边。所有边的容量均为$1$。
于是我们可以得到一张网络流图，如下：

边的容量为$1$保证了同一条边不会同时在多条增广路中，那么任意两条增广路的交点只会是$s$和$t$。此时若求出最大流，那么最大流就是该图的最大匹配，$L\to R$中流量为$1$的边就是最大匹配中的匹配边。

代码参见飞行员配对问题。

2 最大带权匹配

若存在一种匹配方案，使得图上所有点都被匹配，则称这个匹配为二分图的完美匹配。

先考虑存在完美匹配时的情况。

依然是上面的建图思路，并把边权看作费用，$s\to L$和$R\to t$的边费用为$0$。那么显然可以求出最小费用最大流。

把最大边权和转化成最小费用？两种思路：每次延着最长路增广 和 使费用为边权的相反数。

但是此时最小费用其实受最大流的限制，也就是说仅当流最大时才保证费用最小，那么这样求出来的最小费用实际上是完美匹配的最小边权和。为什么呢？当存在完美匹配时，最大流一定是这个完美匹配，那么这时候最小费用才对应着图上的最小边权和，那么也就是完美匹配的最小边权和。

那么怎样求不受边数限制的最大带权匹配？

也就是说要摆脱这个“最大流”的限制。怎么做呢？
每次增广后都记录一下当前的总费用，直到当前流最大，那么所有可能的匹配的边权和我们都已经求出来了，只要把最小（如果费用是边权的相反数）的那个挑出来就好了。

建图的图解如下：

3 最大带权独立集

选出一些节点，使得这些节点都没有边相连，称其为原图的一个独立集。

那么最大带权独立集就是在点有点权的基础上，求出一个点权和最大的独立集。

还是上面的思路。
新建总源$s$，总汇$t$。设二分图的左图为$L$，右图为$R$。将$s$向$L$中的所有节点连边，容量为$L$中节点的点权；$R$中的所有节点向$t$连边，容量为$R$中节点的点权。并将二分图中原有的无向边转化成$L\to R$的有向边，容量无限。

那么有： 最大独立集 = 总点权-最小割（最大流）

割中的边一定是$s\to L$或$R\to t$的边。增广它们等于删掉这些边，相当于删掉$L,R$中的结点。删掉最小割一定会导致图不连通。而在原二分图中，删掉割中的节点及所连接的边，就会导致图上一条边也没有！
那么剩下的节点肯定是独立集。又保证了割最小，所以求得了最大独立集。

图解：