费用流

费用流

费用流

洛谷博客
github
vercel

前置知识：网络流

这里讲最小费用最大流 ( Minimum Cost Maximum Flow, MCMF )

定义

在网络流的基础上，每条边有一个单位费用，每条边的费用是它的流量乘上单位花费。我们用 (u,v,w,c)(u,v,w,c) 来表示从 uu 到 vv 最大流量为 ww 单位费用为 cc 的一条边。

最小费用最大流问题就是要找到一个最大流，使得在流量最大的基础上，它的所有边费用和最小。

方法

讲两种：SSP 与 Primal-Dual

zkw流我不会所以不讲

SSP

非常非常非常简单

在 Dinic 的基础上，贪心沿着费用最小路增广。

注意建反向边时要把费用取相反数。

Primal-Dual

以下所有 wijw_{ij} 指边 (i,j)(i,j) 的费用

原始对偶，好写好调跑得快，就是不知道名字啥意思。

因为反向边的存在，我们不得不面对负权边，所以我们不得不使用死去的 SPFA。但是 SPFA 慢，我们要用 Dijkstra！

为了使边权非负，我们考虑给每条边增减边权，我们想到给每一个点一个势函数 hih_i，每条边的边权变为 wij′=wij+hi−hjw^\prime_{ij}=w_{ij}+h_i-h_j。

令 GG 指每条边 (i,j)(i,j) 权值为 wijw_{ij} 的图，G′G^\prime 指每条边 (i,j)(i,j) 权值为 wij′w^\prime_{ij} 的图，然后我们得到 G′G^\prime 中路径 i1,i2,⋯ ,iqi_1,i_2,\cdots,i_q 长度为

wi1,i2′+wi2,i3′+⋯+wiq−1,iq′=wi1,i2+hi1−hi2+wi2,i3+hi2−hi3+⋯+wiq−1,iq+hiq−1−hiq=wi1,i2+wi2,i3+⋯+wiq−1,iq+hi1−hiq\begin{aligned} &w^\prime_{i_1,i_2}+w^\prime_{i_2,i_3}+\cdots+w^\prime_{i_{q-1},i_q} \\=&w_{i_1,i_2}+h_{i_1}-h_{i_2}+w_{i_2,i_3}+h_{i_2}-h_{i_3}+\cdots+w_{i_{q-1},i_q}+h_{i_{q-1}}-h_{i_q}\\ =&w_{i_1,i_2}+w_{i_2,i_3}+\cdots+w_{i_{q-1},i_q}+h_{i_1}-h_{i_q} \end{aligned}

GG 中的一条路径与 G′G^\prime 中的对应路径仅仅差一个常数，也就是在 GG 中的最短路经过的点就是 G′G^\prime 经过的点。所以我们在 G′G^\prime 上跑 Dijkstra 推流量即可。

接下来是如何维护势函数。我们发现若 did_i 为 GG 中 ss 到 ii 最短路长度，则有 dj≤di+wijd_j\le d_i+w_{ij}，变形一下就是 wij+di−dj≥0w_{ij}+d_i-d_j\ge0，因此 dd 就可以作为初始的势函数 hh。

然后每次跑 Dijkstra 得到的 GG 中的距离 did_i 作为新的 hh 即可。

划重点：Dijkstra 出来的是 G′G^\prime 的距离 di′d^\prime_i，而 di=di′+hs−hi=di′−hid_i=d^\prime_i+h_s-h_i=d^\prime_i-h_i，所以 hi+di′=dih_i+d^\prime_i=d_i，所以代码里是累加。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// P3381 Luogu
// Graph Theory
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

typedef long long ll;

namespace cflow{	// 奇异的空行充满了代码, 112 行

	const int maxn=5005,maxm=50005;
	const ll inf=0x3f3f3f3f3f3f3f3f;

	int n,s,t;

	inline int oth(int x){
		return ((x-1)^1)+1;
	}

	struct edge{
		int u,v; ll w,c; int nxt;
		edge(){}
		edge(int u_,int v_,ll w_,ll c_,int nxt_)
			{ u=u_,v=v_,w=w_,c=c_,nxt=nxt_; }
	}e[2*maxm];
	int fst[maxn],tp=0;

	void addedge(int u,int v,ll w,ll c){
		e[++tp]=edge(u,v,w,c,fst[u]);
		fst[u]=tp;
	}
	void addflow(int u,int v,ll w,ll c){
		addedge(u,v,w,c);
		addedge(v,u,0,-c);
	}

	ll dis[maxn],h[maxn],mxw[maxn];int cnt[maxn],frm[maxn],fre[maxn];
	bool vis[maxn];

	void spfa(){
		static queue<int> q;
		while(!q.empty()){ q.pop(); }

		memset(dis,0x3f,sizeof(dis));
		memset(cnt,0,sizeof(cnt));
		memset(vis,0,sizeof(vis));

		dis[s]=0;vis[s]=1;q.push(s);cnt[s]++;
		while(!q.empty()){
			int u=q.front();q.pop();vis[u]=0;
			if(cnt[u]>n+1){
				break;
			}
			for(int i=fst[u];i!=0;i=e[i].nxt){
				int v=e[i].v;
				ll c=e[i].c;
				if(e[i].w==0){ continue; }
				if(dis[v]>dis[u]+c){
					dis[v]=dis[u]+c;
					if(!vis[v]){ vis[v]=1;q.push(v);cnt[v]++; }
				}
			}
		}
	}

	void clear(){
		memset(cflow::fst,0,sizeof(cflow::fst));cflow::tp=0;
	}
	void init(int n_,int s_,int t_){
		n=n_,s=s_,t=t_;
	}

	struct pr{
		ll dis;int u;pr(){}pr(int u_,ll dis_){u=u_,dis=dis_;}
	};
	bool operator<(pr a,pr b){
		return (a.dis!=b.dis)?(a.dis>b.dis):(a.u>b.u);
	}

	bool dijkstra(){
		static priority_queue<pr> q;
		while(!q.empty()){ q.pop(); }
		memset(dis,0x3f,sizeof(dis));
		dis[s]=0;mxw[s]=inf;q.push(pr(s,0));
		while(!q.empty()){
			int u=q.top().u;q.pop();
			for(int i=fst[u];i!=0;i=e[i].nxt){
				int v=e[i].v;
				ll c=e[i].c+h[u]-h[v],w=e[i].w;
				if(w && (dis[v]>dis[u]+c)){
					dis[v]=dis[u]+c;
					mxw[v]=min(mxw[u],w);
					frm[v]=u;
					fre[v]=i;
					q.push(pr(v,dis[v]));
				}
			}
		}
		return dis[t]!=inf;
	}

	ll mincost,maxflow;

	void MCMF(){

		spfa();
		memcpy(h,dis,sizeof(h));

		mincost=maxflow=0;
		while(dijkstra()){
			ll flow=mxw[t];
			maxflow+=flow;
			mincost+=flow*(dis[t]-h[s]+h[t]);
			for(int i=t;i!=s;i=frm[i]){
				e[fre[i]].w-=flow;
				e[oth(fre[i])].w+=flow;
			}
			for(int i=1;i<=n;i++){
				h[i]+=dis[i];	// 敲重点，累加
			}
		}
	}
}

int n,m,s,t;

int main(){
	
	scanf("%d%d%d%d",&n,&m,&s,&t);
	cflow::n=n; cflow::s=s; cflow::t=t;
	for(int i=1;i<=m;i++){
		int u,v;ll w,c;
		scanf("%d%d%lld%lld",&u,&v,&w,&c);
		if(c<0){
			cflow::addflow(v,u,w,-c);
		}else{
			cflow::addflow(u,v,w,c);
		}
	}

	cflow::MCMF();

	printf("%lld %lld\n",cflow::maxflow,cflow::mincost);

	return 0;

}
讲义 天元
图论 建模 讲义 最小费用最大流 网络流

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！