费用流

费用流全称为最小费用最大流,其求解的问题为:在一个图中,从一个起点到终点运输流量,每条边之间都有单位运输费用。问在最大流的情况下最小的花费是多少。

这是在网络流的基础上将边加上了权值,其求解方法与网络流类似,不过需要先用spfa去求最短路。其总的基本步骤为:建反向边(流量为0,权值为原权值)—>跑spfa—>跑最大流—>直到求解到没有流量为止。前置知识为预先了解网络流

接下来一步一步进行说明。

建反向边

首先依然使用链式前向星来存图,只不过多了几项需要存的数据:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int lnk[maxn];//链式前向星对应的边
int cur[maxn];//复制前向星的数组
int ter[maxm];//每条边连向的节点
int nxt[maxm];//链式前向星下一条边
int cap[maxm];//每条边的当前可用流量
int cost[maxm];//每条边的单位流量费用
int dis[maxn];//最短路
int ret;//最小花费
void add(int u,int v,int w,int c){//从u到v,流量为w,费用为c
ter[++tot]=v;
nxt[tot]=lnk[u];
lnk[u]=tot;
cap[tot]=w;
cost[tot]=c;
}

跑spfa

spfa的意义在于:对于每一单位流量,我们要找到从起点到终点的最小花费,就相当于是从起点到终点的最短路,因此我们只需要跑一边最短路即可。每跑一次后都需要进行重新计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool spfa(int s,int t){
memset(dis,INF,sizeof(dis));
queue<int>que;
que.push(s);
dis[s]=0;
vis[s]=1;
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=0;
for(int i=lnk[u];i;i=nxt[i]){
int v=ter[i];
if(cap[i] && dis[v]>dis[u]+cost[i]){//单位花费即为权值
dis[v]=dis[u]+cost[i];
if(!vis[v]){
que.push(v);
vis[v]=1;
}
}
}
}
return dis[t]!=INF;//是否有解
}

跑最大流

接下来就利用求解出来的最短路的值来跑最大流。注意每次只能在求解出来的最短路上进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int dfs(int u,int t,int flow){
if(u==t) return flow;
vis[u]=1;
int ans=0;
for(int &i=cur[u];i&&ans<flow;i=nxt[i]){//弧优化
int v=ter[i];
//没被访问过(防止跑环) 且 有流量 且 在最短路上
if(!vis[v] && cap[i] && dis[v]==dis[u]+cost[i]){
int x=dfs(v,t,min(cap[i],flow-ans));
if(x){
ret+=x*cost[i];
cap[i]-=x;
cap[i^1]+=x;
ans+=x;
}
}
}
vis[u]=0;
return ans;
}

直到没有流量为止

1
2
3
4
5
6
7
8
int mcmf(int s,int t){//min cost max flow
int ans=0,x;
while(spfa(s,t)){
memcpy(cur,lnk,sizeof(lnk));
while(x=dfs(s,t,INF)) ans+=x;
}
return ans;//ans为最大流量
}

完整代码如下【模板】最小费用最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=10000+10;
const int maxm=100000+10;
int n,m,tot=1;
int lnk[maxn];//链式前向星对应的边
int cur[maxn];//复制前向星的数组
int ter[maxm];//每条边连向的节点
int nxt[maxm];//链式前向星下一条边
int cap[maxm];//每条边的当前可用流量
int cost[maxm];//每条边的单位流量费用
int dis[maxn];//最短路
int ret;//最小花费
bool vis[maxn];
void add(int u,int v,int w,int c){
ter[++tot]=v;
nxt[tot]=lnk[u];
lnk[u]=tot;
cap[tot]=w;
cost[tot]=c;
}
bool spfa(int s,int t){
memset(dis,INF,sizeof(dis));
queue<int>que;
que.push(s);
dis[s]=0;
vis[s]=1;
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=0;
for(int i=lnk[u];i;i=nxt[i]){
int v=ter[i];
if(cap[i] && dis[v]>dis[u]+cost[i]){
dis[v]=dis[u]+cost[i];
if(!vis[v]){
que.push(v);
vis[v]=1;
}
}
}
}
return dis[t]!=INF;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
vis[u]=1;
int ans=0;
for(int &i=cur[u];i&&ans<flow;i=nxt[i]){
int v=ter[i];
if(!vis[v] && cap[i] && dis[v]==dis[u]+cost[i]){
int x=dfs(v,t,min(cap[i],flow-ans));
if(x){
ret+=x*cost[i];
cap[i]-=x;
cap[i^1]+=x;
ans+=x;
}
}
}
vis[u]=0;
return ans;
}
int mcmf(int s,int t){
int ans=0,x;
while(spfa(s,t)){
memcpy(cur,lnk,sizeof(lnk));
while(x=dfs(s,t,INF)) ans+=x;
}
return ans;
}
int main()
{
int s,t;
scanf("%d %d %d %d",&n,&m,&s,&t);
while(m--){
int u,v,w,c;
scanf("%d %d %d %d",&u,&v,&w,&c);
add(u,v,w,c);
add(v,u,0,-c);
}
int ans=mcmf(s,t);
printf("%d %d\n",ans,ret);
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------