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

概念引入

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

将抽象的问题具象化：在一张高速网中有 \(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;
}