题解 P3381 【【模板】最小费用最大流】
2018一维
2019-07-05 13:26:29
# 前言
本文发表于：
- 个人博客：[链接](https://2018haha.github.io)
- 洛谷博客：[链接](https://www.luogu.org/blog/2018--haha/solution-p3381 )
网络流是OI中比较常出现的算法，而最小费用最大流是其最常用的算法之一，阅读本文前，请确保掌握了网络最大流的Dinic的求法，详见[网络最大流](https://2018haha.github.io/2019/06/27/%E7%BD%91%E7%BB%9C%E6%9C%80%E5%A4%A7%E6%B5%81/#more )
# 最小费用最大流算法
## 简介
最小费用最大流（以下简称费用流），是在网络最大流的基础上，给每个边增加了另一个值——费用，代表每流过一个单位的流量，就会耗费这些费用。而费用流算法，就是在求最大流的同时，找出所花费用最小的方案，并求出这个最小费用。
## 实现方法
首先，对于同一个图，它的最大流是一个固定的值，但是有很多方案，而求费用最小的走法，便可以利用**最短路算法**，以费用为最短路的边权。
思考一下，Dinic中的反边思想实际上是让程序可以沿着反边跑回去，达到反悔目的。所以费用流中，反边的费用需要设置成正边的相反数，保证在返回时费用也会还回来。
由于反边有负边权，所以要用~~已死的~~SPFA
把$Dinic$中的$Bfs$改为$SPFA$即可,每次找残量图中$S-T$的最短路径（费用作为边权），并按照$Dinic$的方式增广这条路径。
$Dinic$增广时需要把残量图中流量更改，所以要用能记录路径的$SPFA$
### 建图
```cpp
int head[N],to[N],next[N],f[N],c[N];//f是容量，c是费用
int cnt=1;
void Add(int x,int y,int z,int cost)
{
to[++cnt]=y;
f[cnt]=z;
c[cnt]=cost;
next[cnt]=head[x];
head[x]=cnt;
}
```
### SPFA
```cpp
int dis[N];/*spfa的距离数组*/
int flow[N];/*源点到此处流量*/
int vis[N];
int pre[N];//每个点的前驱
int last[N];
bool Spfa()
{
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(S);
vis[S]=1,dis[S]=0;
pre[T]=-1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=next[i])
{
int v=to[i];
if(f[i]>0 && dis[v]>dis[u]+c[i])//有残量，能松弛
{
dis[v]=dis[u]+c[i];//更新距离
pre[v]=u;//SPFA记录前驱
last[v]=i;//记录边的编号，便于增广时更改边权
flow[v]=min(flow[u],f[i]);
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
return ~pre[T];
}
```
主函数
```cpp
int Flow,Cost;
void Mcmf()
{
while(Spfa())
{
int u=T;
Flow+=flow[T];
Cost+=flow[T]*dis[T];
while(u!=S)//遍历这次的增广路（最短路）
{
f[last[u]]-=flow[T];//更新边权
f[last[u]^1]+=flow[T];
u=pre[u];
}
}
}
```
### 总结
这种费用流算法实际上就是在增广时优先考虑费用（用最短路SPFA实现），保证费用最小（反正由于反边的存在，Dinic怎么流到最后都能流出最大流 ）。
完整代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define next adjagag
using namespace std;
const int N=1000010;
int head[N],to[N],next[N],f[N],c[N];
int cnt=1;
int n,m,S,T;
void Add(int x,int y,int z,int cost)
{
to[++cnt]=y;
f[cnt]=z;
c[cnt]=cost;
next[cnt]=head[x];
head[x]=cnt;
}
int dis[N];
int flow[N];
int vis[N];
int pre[N];
int last[N];
bool Spfa()
{
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
queue<int> q;
q.push(S);
vis[S]=1,dis[S]=0;
pre[T]=-1;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=next[i])
{
int v=to[i];
if(f[i]>0 && dis[v]>dis[u]+c[i])
{
dis[v]=dis[u]+c[i];
pre[v]=u;
last[v]=i;
flow[v]=min(flow[u],f[i]);
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
return ~pre[T];
}
int Flow,Cost;
void Mcmf()
{
while(Spfa())
{
int u=T;
Flow+=flow[T];
Cost+=flow[T]*dis[T];
while(u!=S)
{
f[last[u]]-=flow[T];
f[last[u]^1]+=flow[T];
u=pre[u];
}
}
}
int main()
{
scanf("%d %d %d %d",&n,&m,&S,&T);
for(int i=1;i<=m;i++)
{
int x,y,z,c;
scanf("%d %d %d %d",&x,&y,&z,&c);
Add(x,y,z,c);
Add(y,x,0,-c);
}
Mcmf();
printf("%d %d\n",Flow,Cost);
return 0;
}
```