时隔多日,又一模板收入其中:最小费用最大流。

概念引入

  • 费用:对每条有向边新增的一个属性,费用表示每个经过这条边的一个单位流量将会添加这么多费用。

将抽象的问题具象化:在一张高速网中有 $n$ 个收费站,$m$ 条单向通行的道路,每走完一条道路就会到那边的收费站收费,收费价格会根据你走的哪条路收费,而不是固定的收费点就收固定的钱,这个也很合逻辑吧。然后一条道路最多同行 $w$ 辆车,也就是说这条路一旦走过超过 $w$ 辆车那这条路将不再放行,虽然不符合我们的认知但是他就这么规定了你也没办法嘛对吧。在 $n$ 个收费站有一个源收费站一个目的收费站,问最多有多少辆车能从源收费站到目的收费站,总费用最小的通行方案是多少。

解题步骤

乍一听好像没啥思路,但是从一个司机的角度去考虑,这就会变得简单了,因为对于一个司机来说,我的目标是到达目的收费站且使我花费最少。那么起点终点确定了,每条路收费确定了,收费站之间的道路也确定了,那么我以收费为边权计算我到终点的单源最短路不就可以了么,走单源最短路一定会使得我的花费最少,因为边权是费用,最短在某种意义上就是费用最少啦。

但是我们是不可能为每一个司机考虑的,我们可以搜出一条单源最短路,那么就很容易计算这条路上的总费用和最小流量。那么这一次我就相当于通过了,最小流量 辆车,费用相当于多了 最小流量$\times$ 总费用 。这里就跟网络流有点类似了,我求单源最短路的过程也可以视为找一条增广路。在结果保存之后我们依然要添加反向边,然后对应流量减少,反向边流量增加。但是这里我们还需要注意这个反向边费用是多少呢?其实很好理解,我一辆车过去,再回来,对车来说相当于没过去,也就没有花费虽然实际情况不是这样,所以我们添加反向边的时候要给路径长度为负边权。这样就决定了我们只能考虑某已死算法,虽然你可以给所有边权加上一个最大值使得每个边权为正,最后跑完 $\text{dijkstra}$ 之后再每条边减去这么多。但是实际我写出来并不行,也不知道为什么,但是听说国际公约:网络流不卡 $\text{Dinic}$ 算法,费用流不卡 $\text{spfa}$ 算法。

最后一点需要注意:一条边流量为 $0$ 之后,它应被视为断开。

标程

模板题:P3381

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
87
88
89
#include<bits/stdc++.h>
#define maxn 100005
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int,int> P;
struct eee{
int to;
int w;
int d;
int next;
}edge[maxn];
struct ppp{
int v;
int edge;
}pre[maxn];
int s,t,ans,n,m,cnt;
int root[maxn],dis[maxn],inque[maxn],vis[maxn];
queue<int>q;
inline void add(int x,int y,int w,int d){
edge[++cnt]={y,w,d,root[x]};
root[x]=cnt;
}

bool spfa(){
memset(dis,0x3f,sizeof(dis));//最大初始化
dis[s]=0;
q.push(s);//源点入队
while(!q.empty()){
int u=q.front();
q.pop();
inque[u]=0;
//cout<<u<<endl;
for(int i=root[u];i;i=edge[i].next){
int v=edge[i].to;
if(!edge[i].w)continue;//如果这条边没有流量则跳过
if(dis[v]>dis[u]+edge[i].d){//三角形不等式判定
dis[v]=dis[u]+edge[i].d;
pre[v].v=u;//记录路径
pre[v].edge=i;
if(!inque[v]){//经典spfa
inque[v]=1;
q.push(v);
}
}
}
}
return dis[t]!=inf;
}

void EK(){
int ans=0,w=0;
while(spfa()){
int k=inf;
int f=0;
for(int i=t;i!=s;i=pre[i].v){
k=min(edge[pre[i].edge].w,k);//计算最小流量
f+=edge[pre[i].edge].d; //统计总费用
}
for(int i=t;i!=s;i=pre[i].v){
edge[pre[i].edge].w-=k;//正向边流量-
edge[pre[i].edge^1].w+=k;//反向边流量+
}
ans+=k;//计算流量
w+=k*f;//计算费用
}
cout<<ans<<' '<<w<<endl;
}

void sync(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}

signed main(){
//freopen("P3381_8.in","r",stdin);
sync();
cnt=1;
cin>>n>>m>>s>>t;
while(m--){
int u,v,w,c;
cin>>u>>v>>w>>c;
add(u,v,w,c);
add(v,u,0,-c);//添加负费用的反向边
}
EK();
return 0;
}