关于最小费用最大流的解题

费用=20+2 9=38
画出对应的增广网络 图(可调整量,单位费用)
2
(+3, v4)
2
(+2, v1)
前向,后向都有调整量
只有后向弧可以调整
可调整流，费用
把单位费用作为弧长,用标号法求从s到t的最短路
s:标(0 , )
(1,s)
min{(sv1)}={1,}=1
v1标号:(1,s)
(0, )
标不下去,已经找不到增广路
下方案总费用=14+3 3+11+43+2 4=34
求最小费用最大流 (容量,费用) 弧上数据(uj,cj)
uj 为弧的容量
Cj 为从这条弧运 送物资的费用
注意:
这两图 的权的 含义不 同
解: 设图中每条弧上的流量fj都为零,得到下图 (可调整流量,费用)
画出与上图对应的增广网络图,弧上权为(弧上流量的可调整 量,单位费用)
Min{(v1v3)(v1v4)}={1+4,1+3}=4
(4,v3)
(4, v1)
v4标号:(4, v1) Min{ (v4t)(v1v3)}={4+5 , 1+4}=5
v3标号:(5, v1) v2标号:(4, v3)
Min{(v3t)(v4t)(v3v2)}={5+3,4+5,5-1}=4 Min{(v3t)(v4t)(v2v4)}={5+3,4+5,4+6}=8
容量、费用、流量
(+1, v1)
1
3
(+2, v3)
前向,后向都有调整量 只有后向弧可以调整
可调整流，费用
把单位费用作为弧长,用标号法求从s到t的最短路

网络流：最小费用最大流（最简单的算法）最小费用流在OI 竞赛中应当算是比较偏门的内容，但是NOI2008 中employee 的突然出现确实让许多人包括zkw 自己措手不及。

可怜的zkw 当时想出了最小费用流模型，可是他从来没有实现过，所以不敢写，此题0 分。

zkw 现在对费用流的心得是：虽然理论上难，但是写一个能AC 题的费用流还算简单。

先贴一个我写的employee 程序：只有不到70 行，费用流比最大流还好写～程序代码:C++#include <cstdio>#include <cstring>using namespace std;const int maxint=~0U>>1;int n,m,pi[550]={0},cost=0;bool v[550]={0};struct etype{int t,c,u;etype *next,*pair;etype(){}etype(int t_,int c_,int u_,etype* next_):t(t_),c(c_),u(u_),next(next_){}void* operator new(unsigned,void* p){return p;}} *e[550],*eb[550];int aug(int no,int m){if(no==n)return cost+=pi[1]*m,m;v[no]=true;for(etype *&i=e[no];i;i=i->next)if(i->u && !v[i->t] && pi[i->t]+i->c==pi[no])if(int d=aug(i->t,m<i->u?m:i->u))return i->u-=d,i->pair->u+=d,d;return 0;}bool modlabel(){int d=maxint,c;for(int i=1;i<=n;++i)if(v[i])for(etype *j=eb[i];j;j=j->next)if(j->u && !v[j->t])if((c=j->c-pi[i]+pi[j->t])<d)d=c;if(d==maxint)return false;for(int i=1;i<=n;++i)if(v[i])pi[i]+=d,e[i]=eb[i];return true;}int main(){freopen("costflow.in","r",stdin);freopen("costflow.out","w",stdout);scanf("%d %d",&n,&m);etype *Pe=new etype[m+m];while(m--){int s,t,c,u;scanf("%d%d%d%d",&s,&t,&u,&c);e[s]=new(Pe++)etype(t, c,u,e[s]);e[t]=new(Pe++)etype(s,-c,0,e[t]);e[s]->pair=e[t];e[t]->pair=e[s];}memmove(eb,e,sizeof(e));do do memset(v,0,sizeof(v));while(aug(1,maxint));while(modlabel());printf("%d\n",cost);return 0;}程序代码:CB大牛翻译的PASCALvarn,m,i,l,s,t,c,cost,u:longint;v:array[0..600]of boolean;dis:array[0..600]of longint;e_n,e_t,e_c,e_u,e_p,e_x:array[0..250000]of longint;function min(a,b:longint):longint;beginif a>b then exit(b);exit(a);end;procedure addedge(s,t,c,u,k:longint);begininc(l);e_n[l]:=e_n[s];e_n[s]:=l;//下一条边e_t[l]:=t;//边的另一端e_c[l]:=c;//边的费用e_u[l]:=u;//边的容量e_p[l]:=l+k;//对应的边end;procedure build(s,t,c,u:longint);beginaddedge(s,t,c,u,1);addedge(t,s,-c,0,-1);end;function aug(no,m:longint):longint;vari,d:longint;beginif no=n then begininc(cost,m*dis[1]);exit(m);end;v[no]:=true;i:=e_x[no];while i<>0 do beginif (e_u[i]>0)and(not v[e_t[i]])and(dis[e_t[i]]+e_c[i]=dis[no]) then begind:=aug(e_t[i],min(m,e_u[i]));if d>0 then begindec(e_u[i],d);inc(e_u[e_p[i]],d);e_x[no]:=i;exit(d);end;end;i:=e_n[i];end;e_x[no]:=i;exit(0);end;function modlabel:boolean;vard,i,j:longint;begind:=maxlongint;for i:=1 to n do if v[i] then beginj:=e_n[i];while j<>0 do beginif (e_u[j]>0)and(not v[e_t[j]])and(e_c[j]-dis[i]+dis[e_t[j]]<d) then d:=e_c[j]-dis[i]+dis[e_t[j]];j:=e_n[j];end;end;if d=maxlongint then exit(true);for i:=1 to n do if v[i] then beginv[i]:=false;inc(dis[i],d);end;exit(false);end;beginassign(input,'coflow.in');reset(input);assign(output,'coflow.out');rewrite(output);readln(n,m);l:=n;for m:=m downto 1 do beginreadln(s,t,u,c);build(s,t,c,u);end;repeatfor i:=1 to n do e_x[i]:=e_n[i];while aug(1,maxlongint)>0 do fillchar(v,sizeof(v),0);until modlabel;writeln(cost);close(output);end.这里使用的是连续最短路算法。

v2
v3
(10, 0) ①流量调整量 总流量v(f 总流量v(f(1))=5
v2
v3
=min{8-0,5-0,7ε1=min{8-0,5-0,7-0}=5 ②最小费用增广链的费用 ∑bij=1+2+1=4 ③新的可行流为f(1),总费 新的可行流为f =4× 用b1=4×5=20
vs →v2 →v1 →vt
2、最小费用流 对于一个费用容量网络，具有相同 对于一个费用容量网络， 流量 v(f) 的可行流中，总费用b(f)最小的 的可行流中，总费用b(f)最小的 可行流称为该费用容量网络关于流量 v(f) 的最小费用流，简称流量为 v(f) 的最小 的最小费用流，简称流量为 费用流。 费用流。
3、增广链的费用 当沿着一条关于可行流 f 进行调整，得到新的可行流 f 进行调整， 称 b( f ) − b( f ) 的增广 ，则 链（流量修正路线）µ，以修正量 流量修正路线） ，以修正量ε=1 增广链µ的费用。 为增广链µ的费用。
v2
v3
即是f 的最小费用增广链。 即是f(1)的最小费用增广链
第3次迭代
-4 4
v1
-2 6
பைடு நூலகம்
-1
(10, 2)
v1
(7, 7) (2, 0)
vs
-1
1
vt
2 (8, 8)
vs
(5, 5)
vt
(4, 3)
v2
3
v3
①零流弧保持原边，非饱和非 零流弧保持原边， 零流弧增添后向弧， 零流弧增添后向弧，饱和弧去 掉原边增添后向弧 ②用列表法求得最短路
增广费用网络图的 增广费用网络图的构造方法 将流量网络中的每一条弧（ 将流量网络中的每一条弧（vi,vj）都看 作一对方向相反的弧，并定义弧的权数如 作一对方向相反的弧， 下： vi (cij,fij) c vj

最小费用最大流问题例题讲解
最小费用最大流问题（Minimum Cost Maximum Flow Problem）是一种在特定的多媒体网络中传送给定体积的流量，使总花费最小化的一种算法。

它能满足一些实际生活中的求解，比如电力系统的供求、工厂的物料的分配和两地之间的物品的运输问题，以及更加复杂的产品开发和行业分工中的分布问题等等。

最小费用最大流问题的目标是在满足给定的最大流量要求的前提下，找出具有最小成本的流量方案。

这种问题的解决步骤如下：
1. 在图形中定义网络：用图形表示整个网络，每条边的容量是边上的流量上限。

2. 尝试找出最大流量：在不超过容量限制的前提下，找出输出流量最大的允许方案，也就是最小费用最大流量。

3. 计算最小成本：对所有边的成本进行总结，计算出最小成本。

下面以一个最小费用最大流问题的例题来说明：
假设有一个三角形的网络，它由一个源点S、一个汇点T、一个中间点O以及三条边组成，边的名字分别是SO、OT、OS，它们的容量分别是10、15和5，费用分别是5、3和2。

要求我们在此条件下求解最小费用最大流问题。

解：首先，我们可以求出最大流量：在边SO的容量为10时，我们可以将费用最小的边OT累加，得到最大流量值为10+3=13。

接下来，计算最小费用：根据上述算法，所有边的费用应该都大于等于0，才能累加而得到最大流量。

也就是说，最小费用为
5+3+2=10。

最后，最小费用最大流问题的解为：最大流量13，最小成本10。

(
vs
(
5,2)
(
(
2,6)
8,1)
V2 10,3)ቤተ መጻሕፍቲ ባይዱV3
4,2)
第一轮：f 0为初始可行流，作相应的费用有向图网络L(f 0)，如 图（a）。 在L(f 0)上用DijksTra标号法求出由vs到vt的最短路（最小费用链） 0 m i n 8，5， 5 7 μ0=(vs,v2,v1, （ vt)v ，并对 μ 按 进行流量的调整， 0 ， v ） ，（ v ， v ） ，（ v ， v ） s 2 0 2 1 0 1 t 0 由于， (1) (1) 所以有 fs2 f12 f1t(1) 5，其余不变，得新的可行流f1的流量 有向图（b）。
vs
vt
2.下表给出某运输问题的产销平衡表与单位运价 表。将此问题转化为最小费用最大流问题，画出网 络图并求数值解。 2 3 产量 1 产地 销地
A B 销量 20 30 4 24 22 5 5 20 6 8 7
最小总费用为240
(20,8) A (0,8) s (30,7) (0,7) (5,8) (24,8)
4
vt
vs
1
6
2
2
v1
(7,5)
（2，0）
（10，0）
vt
(4，0)
v2
V(f
1)
(a) = 5
3
v3 vs
(8，5)
w(f0)
（5，5）
v2
(10,0)
v3
(b) f 1
v1 vs
(8，5)
(7,5)
（2，0）
（10，0）
vt
(4，0) 4
v1
vs

近似算法和启发式算法
要点一
近似算法
近似算法是一种用于求解NP-hard问题的有效方法，它可 以在多项式时间内找到一个近似最优解。最小费用最大流 问题的近似算法包括Ford-Fulkerson算法、EdmondsKarp算法等。
要点二
启发式算法
启发式算法是一种基于经验或直观的算法，它可以在合理 的时间内找到一个近似最优解。最小费用最大流问题的启 发式算法包括基于增广路径的算法、基于贪婪的算法等。
研究如何将最小费用最大流问题 应用于计算机科学领域，例如计 算机网络、云计算等。
物理学
研究如何借鉴物理学中的理论和 思想，解决最小费用最大流问题， 例如利用流体动力学中的思想来 研究网络中的流。
谢谢观看
Hale Waihona Puke 06未来研究方向和展望算法优化和改进
动态规划算法
研究如何优化动态规划算法，减少时间复杂度 和空间复杂度，提高求解效率。
近似算法
研究近似算法，在保证求解质量的前提下，提 高求解速度。
并行计算和分布式计算
研究如何利用并行计算和分布式计算技术，加速最小费用最大流问题的求解。
新的问题定义和模型
考虑更复杂的情况
和技术。
有界容量和无界容量
总结词
有界容量和无界容量是指在网络中节点之间 的容量是否有限制。
详细描述
在最小费用最大流问题中，如果节点之间的 容量有限制，即为有界容量问题；如果节点 之间的容量没有限制，即为无界容量问题。 有界容量问题可以通过增广路径算法、预流 推进算法等求解，而无界容量问题则需要采
用其他算法和技术进行求解。
算法概述
最小费用最大流问题是一种网络流问 题，旨在在给定有向图中寻找一条路 径，使得从源节点到汇点之间的总流 量最大，同时满足每个节点的流入量 等于流出量，以及每条边的容量限制。

图论专题小结：最小费用最大流算法一，给定流量F，求最小费用题意：网络中有两台计算机s,t。

现在每秒钟要从s到t传输大小为F的数据到t。

该网络中一共有N台计算机，其中有一些靠单向电缆相连接每条电缆用（from,to,cap,cost）表示从from发送给to，最大容量是cap，单位传输费用是cost。

问传输数据最小的花费是多少？解决最小费用流的一般思路是：每次都沿着最短路进行增广，增广一次之后累加本次增广的总费用，同时修改剩余的流量F，当F≤0时或dist[t]==INF时退出。

利用改进的Dijkstra算法求解（1）概述：题目要求在存在流量为F的前提下，总花费最少。

这类问题就是最小费用流问题。

该问题可以采用加入“势函数”后的Dijkstra算法解决。

因为对于每条边e=(u,v)，有如下事实成立：h(v)≤h(u)+e.cost(其中h[u]表示s到u的最短距离)。

因此令dist[v]=dist[u]+e.cost+h[u]-h[v],。

那么所有的dist值必然大于等于0，这样就能用Dijkstra算法求解了。

下面代码中用了一个优先队列，每次优先出列dist值小的元素。

整个算法的时间复杂度是O(F*ElogV)（F是流量，E是边数，V是顶点数）。

1.#include<iostream>2.#include<algorithm>3.#include<string>4.#include<sstream>5.#include<set>6.#include<vector>7.#include<stack>8.#include<map>9.#include<queue>10.#include<deque>11.#include<cstdlib>12.#include<cstdio>13.#include<cstring>14.#include<cmath>15.#include<ctime>16.#include<functional>ing namespace std;18.19.#define N 100020.#define INF 10000000021.typedef pair<int, int>P;//first保存最短距离，second保存顶点的编号22.23.struct Edge24.{25.int to, cap, cost, rev;//终点，容量（指残量网络中的），费用，反向边编号26.Edge(int t, int c, int cc, int r) :to(t), cap(c), cost(cc), rev(r){}27.};28.int V;//顶点数29.vector<Edge>G[N];//图的邻接表30.int h[N];//顶点的势31.int dist[N];//最短距离32.int prevv[N];//最短路中的父结点33.int preve[N];//最短路中的父边34.35.void addedge(int from, int to, int cap, int cost)36.{37.G[from].push_back(Edge( to, cap, cost,G[to].size()));38.G[to].push_back(Edge( from, 0, -cost, G[from].size() - 1 ));39.}40.int min_cost_flow(int s, int t, int f)//返回最小费用41.{42.int res = 0;43.fill(h, h + V, 0);44.while (f>0)//f>0时还需要继续增广45.{46.priority_queue<P, vector<P>, greater<P> >q;47.fill(dist, dist + V, INF);//距离初始化为INF48.dist[s] = 0;49.q.push(P(0, s));50.while (!q.empty())51.{52.P p = q.top(); q.pop();53.int v = p.second;54.if (dist[v]<p.first)continue;//p.first是v入队列时候的值，dist[v]是目前的值，如果目前的更优，扔掉旧值55.for (int i = 0; i<G[v].size(); i++)56.{57.Edge&e = G[v][i];58.if (e.cap>0 && dist[e.to]>dist[v] + e.cost + h[v] - h[e.to])//松弛操作59.{60.dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];61.prevv[e.to] = v;//更新父结点62.preve[e.to] = i;//更新父边编号63.q.push(P(dist[e.to], e.to));64.}65.}66.}67.if (dist[t] == INF)//如果dist[t]还是初始时候的INF，那么说明s-t不连通，不能再增广了68.return -1;69.for (int j = 0; j<V; j++)//更新h70.h[j] += dist[j];71.int d = f;72.for (int x = t; x != s; x = prevv[x])73. d = min(d, G[prevv[x]][preve[x]].cap);//从t出发沿着最短路返回s找可改进量74. f -= d;75.res += d*h[t];//h[t]表示最短距离的同时，也代表了这条最短路上的费用之和，乘以流量d即可得到本次增广所需的费用76.for (int x = t; x != s; x = prevv[x])77.{78.Edge&e = G[prevv[x]][preve[x]];79. e.cap -= d;//修改残量值80.G[x][e.rev].cap += d;81.}82.}83.return res;84.}85.86.int main()87.{88.freopen("t.txt", "r", stdin);89.int m;90.while (cin >> V >> m)91.{92.for (int i = 0; i<m; i++)93.{94.int from, to, cap, cost;95.cin >> from >> to >> cap >> cost;96.addedge(from, to, cap, cost);97.}98.int s, t, f;99.cin >> s >> t >> f;100.cout << min_cost_flow(s, t, f) << endl;101.}102.return 0;103.}104.二，网络输出最大流时，求出最小的费用这就是最小费用最大流问题：既要求出最大流，又要求出达到最大流时候的最小费用。

利用lingo程序求最小费用最大流通常求最小费用最大流问题是分两个阶段：1，先求最大流。

2，再在最大流的基础上求最小费用流。

以下图为例。

其中如（5，8）=（容量，费用）。

求从S到T的最小费用最大流。

1，先求最大流，lingo程序为：MODEL:sets:nodes/s,1,2,3,t/;arcs(nodes,nodes)/s,1 s,2 1,t,1,3 2,1 2,3 3,t/:c,f;endsetsdata:c= 5 8 4 3 2 10 8;enddatamax = flow;@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)|i #eq# 1:f(i,j)) = flow;@for(arcs:@bnd(0,f,c));END结果是，最大流为12，2，再在最大流的基础上求最小费用流。

程序为：MODEL:sets:nodes/s,1,2,3,t/: ;arcs(nodes,nodes)/s,1 s,2 1,t,1,3 2,1 2,3 3,t/:b,c,f;endsetsdata:flow=12;b=8 7 9 2 5 9 4 ;c=5 8 4 3 2 10 8;enddatamin=@sum(arcs:b*f);@for(nodes(i)|i #ne# 1 #and# i #ne#@size(nodes):@sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0);@sum(arcs(i,j)|i #eq# 1:f(i,j)) = flow;@for(arcs:@bnd(0,f,c));END结果是:Global optimal solution found.Objective value: 218.0000Infeasibilities: 0.000000Total solver iterations: 0Variable Value Reduced CostF( S, 1) 5.000000 -6.000000F( S, 2) 7.000000 0.000000F( 1, T) 4.000000 0.000000F( 1, 3) 3.000000 0.000000F( 2, 1) 2.000000 -2.000000F( 2, 3) 5.000000 0.000000 F( 3, T) 8.000000 -3.000000现利用lingo的子模型功能，将2个程序合二为一，可直接算出最小费用流。

c67 = 7 − P = 7 - 6 = 1
通过第1次修改，得到图3。
图3 返回步骤①，进行第2次修改。
次修改： 第2次修改 次修改 选定①—②—⑤—⑦，在这条路中，由 于 P = c25 = 3 ，所以，将 c12 改为2 ， 25 改 c 为0，c57 改为5，c 21 、 52 、 75 改为3。修改后 c c 的图变为图4。
x12 + x13 + x14 = x57 + x67 = f
x12 + x32 x + x 23 13 x14 + x34 x + x 35 25 x36 + x 46 = x 23 + x 25 = x32 + x34 + x35 + x36 = x 46 + x65 = x56 + x57 + x56 = x65 + x67
所以取 P = c13 = 6 。
③在路①—③—⑥—⑦中，修改每一 条弧的容量
c13 = 6-P = 6-6 = 0
c36 = 7 − P = 7 - 6 = 1
c31 = 0 + P = 0 + 6 = 6
c63 = 0 + P = 0 + 6 = 6
c76 = 0 + P = 0 + 6 = 6
f = f 0 ≤ f max
（15）
使其代价最小，即
d=
( i , j )∈V
∑d
ij
xij = min
（16）
式中：d ij 指单位车辆数通过弧 (i, j )的代价。
图11 代价条件
图1 约束条件

−bij +∞
当
f
(K ij
−1
)>
0
当
f
(K ij
−1
)=0
上述定义式的含义是：
零流弧（
f
(K ij
−1)=0
）上，在其对应位置构造与其方向相同且费用为
bij
的弧；
对于饱和弧（
f
(K ij
−1)=c ij
），在其对应位置构造与其方向相反且费用为-bij
的弧；
对于非饱和且非零流弧（
0<
f
(K−1) ij
因 f (s22)=2< cs2=10 ，所以， w(s22)=bs 2=4 。因 f (s22)>0 ，所以， w(22s)=−bs2=−4 。
因 f (s23)=5< cs3=8 ，所以， w(s23)=bs 3=1 。因 f (s23)>0 ，所以， w(32s)=−bs 3=−1 。
因 f 3(22)=5=c32=5 ，所以， w(322)=+∞ 。因 f 3(22)>0 ，所以， w(223)=−b32=−2 。
根据公式：
{ w(ijK −1)=
bij +∞
当
f
(K−1) ij
<
c
ij
当
f
= (K−1)
ij
cij
{ w(jKi −1)=
−bij +∞
当
f
(K ij
−1
)>
0
当
f
(K ij
−1
)=0
因为对任意(vi,vj)， f i(j0)=0 ，所以 w(ij0)= bij , w(j0i )=+∞ 。

i):f(j,i))=0; ); @sum(edge(i,j)|i#eq#@index(s):f(i,j)) =vf; @sum(edge(j,i)|i#eq#@index(t):f(j,i)) =vf; @for(edge(i,j):@bnd(0,f(i,j),u(i,j))) ; end

min
( i , j )E

cij fij ;
s.t.
jV ( i , j )E

fij
jV ( j ,i )E

v f , i s , f ji v f , i t , 0, i s, t.
0 fij uij ,(i, j ) E.
LINGO 程序求解 model: sets: points/s,v1,v2,v3,v4,t/; edge(points,points) /s,v1 s,v2 v1,v2 v1,v3 v2,v4 v3,v2 v3,t v4,v3 v4,t/:c,u,f; endsets data: c=2 8 5 2 3 1 6 4 7; u=8 7 5 9 9 2 5 6 10; vf=14; enddata min=@sum(edge(i,j):c(i,j)*f(i,j)); @for(points(i)|i#ne#@index(s) #and# i#ne#@index(t): @sum(edge(i,j):f(i,j))-@sum(edge(j,
最小费用最大流问题
例 本例是最大流问题的延伸，由于输油管道的长短不 一，或地质等原因，使每条管道上运输费用也不相 同，因此，除考虑输油管道的最大流外，还需要考 虑输油管道输送最大流的最小费用，下图所示是带 有运输费的网络，其中第 1 个数字是网络的容量， 第 2 个数字是网络的单位运费.

最小费用最大流问题解答
【王宇鑫 10111856】
分布求出1到6的通路，并且计算每一种的费用和流量。

（1）1→3→5→6 （2）1→2→4→6
单位费用为2+2+6=10 单位费用为8+3+7=18 饱和流量为5 饱和流量为7
（3）1→3→2→4→6 （4）1→3→2→4→5→6
单位费用为2+5+3+7=17 单位费用为2+5+3+4+6=20 饱和流量为5 饱和流量为5 （5）1→3→5→2→4→6 （6）1→2→4→5→6
单位费用为2+2+1+3+7=15 单位费用为8+3+4+6=21 饱和流量为2 饱和流量5 则可以获得下表：
由此可知：
当05f <≤时，选择1号路线；
当57f <≤时，选择1号与2号混合，流量超过5的部分使用2号路线；
当78f <≤时，选择1号、2号与3号，超过7的部分从3号路走（3号由于1→3路径只能流经1单位的流量）；
当814f <≤时，选择1号、2号、3号与4号路线,8～14的部分从4号走；
此时已经饱和，在无法加大流量了。

则最大流量为14
⨯+⨯+⨯+⨯=+++=
最小费用为510215117618503017108205画出分段的图像
不同流量下的成本曲线
则最后的结果图为：。

最⼩费⽤最⼤流：⼆分答案（bushi）最⼩费⽤最⼤流问题前置知识关于⽹络最⼤流, 这是本博客需要⽤到的两个算法:另外还有效率更⾼, 可是最⼩费⽤最⼤流不会⽤到的两个算法:前置知识就只有第⼀篇博客的内容, 需要提前学习完再来看费⽤流.简介最⼩费⽤最⼤流问题, 简称费⽤流问题, Wikipedia 中的名称是: "Minimum-cost flow problem", 缩写为 "MCFP".问题给出⼀个⽹络, 每条边除了有容量属性外, 还有⼀个属性: 单位流量费⽤. 也就是说, ⼀条边的费⽤是流经这条边的流量和这条边单位流量费⽤的乘积. 要求给出保证最⼤流的情况下的最⼩费⽤.EK·改EK 算法就是每次⽤ BFS 在残量⽹络上找到⼀条可以增⼴的路并且增⼴它. 为了防⽌反复横跳, 我们使⽤ BFS ⽽不是 DFS 寻找增⼴路, 单条增⼴路寻找复杂度O(n+m).所以保证最⼤流, 不需要考虑增⼴路是怎么找的, 只要找到就可以, 所以可以使⽤最短路算法, 每次以S为起点, 以单位花费为边权, 每次求S 到T的最短路, 这个最短路长度乘上这条增⼴路的流量计⼊答案, 然后进⾏下⼀轮的增⼴.算法选择⽅⾯, 因为⼀条边的回边的边权是它的边权的相反数, 所以残量⽹络存在负权, 对于有负权的图的最短路, 我们使⽤ SPFA 算法.Dinic·改Dinic ⼀次求多条增⼴路, ⽽ SPFA 也是⼀次求S到所有点的最短路, 所以两者也可以结合.具体操作是每次 BFS 分层的过程改为求S的单源最短路的过程. 在 DFS 时的规则也有所改变, 传统的 Dinic 中, 我们只允许流从⼀个点, 流向深度⽐它⼤ 1 的点, 是为了保证流不会反复横跳 (我们设定的⼀切规则都是为了规范流的⽅向⽽避免反复横跳, 从算法⽅⾯印证了规则之于⾃由的重要性). 在改进版算法中, 我们使⽤最短路来规范流的流动, 只要保证⼀条边是S到这条边的终点的最短路的⼀部分, 这条路就能⾛.这个规则既保证了我们的选择⼀定是最短路, ⼜保证了流的有序性, ⽽且不破坏 Dinic 的特性: 多路增⼴.实现起来也可以说⽐较写意, 但是需要注意的是, DFS 的过程和⼀般的 Dinic 相⽐增加了⼀个InQue标记.这是因为最短路为序相⽐深度为序来说, 边权对顺序是有影响的, 也就是说当⼀条边和它的回边都有流量的时候, 它们构成⼀个零环, 意思是流量在这两点之间⽆论⾛⼏个来回, 花费都不变.为了避免这种情况, 我们像 SPFA ⼀样使⽤InQue标记, 防⽌增⼴路径上⼀个点出现两次.unsigned m, n, Hd, Tl;int C, D, Flow(0), Cost(0), Tmp(0);struct Node;struct Edge {Node *To;Edge *Nxt;int Value, Contain;}E[100005], *CntE(E - 1);struct Node {Edge *Fst;int Dist;char InQue;}N[5005], *S, *T, *A, *B, *Q[5005];char SPFA() {Tl = Hd = 0;for (register unsigned i(1); i <= n; ++i) N[i].Dist = 0x3f3f3f3f;Q[++Tl] = S;S->Dist = 0;S->InQue = 1;register Node *x;while (Hd ^ Tl) {++Hd; if(Hd > 5000) Hd -= 5000;x = Q[Hd];x->InQue = 0;register Edge *Sid(x->Fst);while (Sid) {if(Sid->Contain && Sid->To->Dist > x->Dist + Sid->Value) {Sid->To->Dist = x->Dist + Sid->Value;if(!(Sid->To->InQue)) {++Tl; if(Tl > 5000) Tl -= 5000;Q[Tl] = Sid->To;Sid->To->InQue = 1;}}Sid = Sid->Nxt;}}return (T->Dist < 0x3f3f3f3f);}int DFS(Node *x, int Come){if(x == T) return Come;x->InQue = 1;register Edge *Sid(x->Fst);register unsigned Go, Flew(0);while (Sid) {if(Sid->To->Dist == x->Dist + Sid->Value && Sid->Contain && (!(Sid->To->InQue))) {Go = DFS(Sid->To, min(Sid->Contain, Come));Sid->Contain -= Go;Come -= Go;E[(Sid - E) ^ 1].Contain += Go;Cost += Sid->Value * Go;Flew += Go;}if(!Come) break;Sid = Sid->Nxt;}x->InQue = 0;return Flew;};int main() {n = RD(), m = RD(), S = N + RD(), T = N + RD();for (register unsigned i(1); i <= m; ++i) {A = N + RD(),B = N + RD(),C = RDsg(),D = RDsg();(++CntE)->Nxt = A->Fst;A->Fst = CntE;CntE->Contain = C;CntE->Value = D;CntE->To = B;(++CntE)->Nxt = B->Fst;B->Fst = CntE;CntE->Value = -D;CntE->To = A;}while (SPFA()) Flow += DFS(S, 0x7fffffff);printf("%d %d\n", Flow, Cost);return Wild_Donkey;}改·改实际上叫做 "Primal-Dual Algorithm" (原始对偶算法).就像59·改和59关系不⼤⼀样, 这个算法虽然名字原始, 但是我⽆论如何也不明⽩它和对偶有什么关系, 如果让我为他取名, 我觉得应该叫做:队列优化的Bellman_Ford和Dijkstra最短路变化量累加求最⼩费⽤最⼤流联合算法由于 SPFA 的最坏复杂度可以达到O(nm), 所以相当于在原算法的基础上增加了⼀个因⼦m, 可以说毫⽆效率可⾔.所以考虑使⽤ Dijkstra, 但是图中有负权, Dijkstra 很难得到正确结果.算法效率低是因为运⾏了多次 SPFA, 但是如果我们只运⾏⼀次 SPFA, 算法效率也是不受影响的.⼀开始跑⼀遍 SPFA, 将S到每个点的最短路求出, 记为h, 我们称h x为点x的势.每次跑最短路, 发现因为残量⽹络越来越残, S到其它点的最短路只能变得更长, 不能变得更短.每次跑 Dijkstra 之前, 假设我们已经求出了每个点的势, 也就是这个残量⽹络变得这么残之前的最短路, 那么规定每条边 (a,b) 的权值|(a,b)|′=|(a,b)|+h a−h b.因为上⼀次 (a,b) 之间的最短路⼀定不会⽐ |(a,b)| 更长, 否则最短路就变成 |(a,b)| 了, 所以容易知道h b−h a≤|(a,b)|, 整理得|(a,b)|′=|(a,b)|+h a−h b≥0, 这样, 边权⼤于 0, 我们就能使⽤ Dijkstra 了.⼀条路径的权值和就变成了它们原来的权值之和加上起点的势再减去终点的势, 其意义是这条路径的起点终点之间的最短路在上次增⼴之后增长了多少. 也就是说, 我们⽤ Dijkstra 求的是⼀个增长量. 是最短路的导数所以从新的权值求得的最短路求真正的最短路的⽅法也变得明了了, 就是⽤⼀开始 SPFA 求的最短路加上每⼀次增⼴后 Dijkstra 求的最短路的总和, 就是当前真正的最短路.这样再拉去跑 Dinic/EK, 就和上⾯两个算法⼀样了, 但是⽹上的⽅法貌似都是⽤ EK, 但是理论上我们有了最短路, 就能像前⾯Dinic·改⼀样多路增⼴.于是我就把 Dinic + Dijkstra + SPFA 写出来了, 很遗憾, 它获得了⽐上⾯的程序更低的效率.unsigned m, n, Hd, Tl;int C, D, Flow(0), Cost(0), Tmp(0);struct Node;struct Edge {Node *To;Edge *Nxt;int Vnew, Value, Contain;}E[100005], *CntE(E - 1);struct Node {Edge *Fst;int Dist, h;char InQue;}N[5005], *S, *T, *A, *B, *Q[5005];struct Que {Node *P;inline const char operator<(const Que &x) const{return this->P->Dist > x.P->Dist;}}QTmp;priority_queue <Que> Qu;void SPFA() {Tl = Hd = 0;for (register unsigned i(1); i <= n; ++i) N[i].h = 0x3f3f3f3f;Q[++Tl] = S;S->h = 0;S->InQue = 1;register Node *x;while (Hd ^ Tl) {++Hd; if(Hd > 5000) Hd -= 5000;x = Q[Hd];x->InQue = 0;register Edge *Sid(x->Fst);while (Sid) {if(Sid->Contain && Sid->To->h > x->h + Sid->Value) {Sid->To->h = x->h + Sid->Value;if(!(Sid->To->InQue)) {++Tl; if(Tl > 5000) Tl -= 5000;Q[Tl] = Sid->To;Sid->To->InQue = 1;}}Sid = Sid->Nxt;}}}int DFS(Node *x, int Come){if(x == T) return Come;x->InQue = 1;register Edge *Sid(x->Fst);register unsigned Go, Flew(0);while (Sid) {if(Sid->To->h == x->h + Sid->Value && Sid->Contain && (!(Sid->To->InQue))) {Go = DFS(Sid->To, min(Sid->Contain, Come));Sid->Contain -= Go;Come -= Go;E[(Sid - E) ^ 1].Contain += Go;Cost += Sid->Value * Go;Flew += Go;}if(!Come) break;Sid = Sid->Nxt;}x->InQue = 0;return Flew;};char Dijkstra () {for (register unsigned i(1); i <= n; ++i) N[i].Dist = 0x3f3f3f3f;QTmp.P = S, Qu.push(QTmp);S->Dist = 0;S->InQue = 1;register Node *x;while (Qu.size()) {x = Qu.top().P;Qu.pop();x->InQue = 0;register Edge *Sid(x->Fst);while (Sid) {Sid->Vnew = Sid->Value + x->h - Sid->To->h;if(Sid->Contain && Sid->To->Dist > x->Dist + Sid->Vnew) { Sid->To->Dist = x->Dist + Sid->Vnew;if(!(Sid->To->InQue)) {QTmp.P = Sid->To;Qu.push(QTmp);Sid->To->InQue = 1;}}Sid = Sid->Nxt;}}for (register unsigned i(1); i <= n; ++i) N[i].h += N[i].Dist;return (T->h < 0x3f3f3f3f);}int main() {n = RD(), m = RD(), S = N + RD(), T = N + RD();for (register unsigned i(1); i <= m; ++i) {A = N + RD(),B = N + RD(),C = RDsg(),D = RDsg();(++CntE)->Nxt = A->Fst;A->Fst = CntE;CntE->Contain = C;CntE->Value = D;CntE->To = B;(++CntE)->Nxt = B->Fst;B->Fst = CntE;CntE->Value = -D;CntE->To = A;}SPFA();do {Flow += DFS(S, 0x7fffffff);} while(Dijkstra());printf("%d %d\n", Flow, Cost);return Wild_Donkey;}Processing math: 100%。

, ,
若(vi 若(vi
, ,
v v
j j
) )
,
fij ,若(vi , v j ) .
去掉全部旳标号,对新旳可行流 f ' { fij '}, 重新进入标号过程.
Back
continued
算 例 用标号法求右下图所示网络旳最大流.弧旁旳数是 (cij , fij ).
解:(一)标号过程
b(
f
*)
min f
bij
(vi ,v j )A
f ij
怎么求解这个问题?
1、定义 增广链 旳费用为 bij bij
结论:若 f 是流量为v( f )旳全部可行流中费用最小者,而 是有关 f 旳全部增广链中费用最小旳增广链,则沿 去调 整 f ,得到旳可行流 f ' ,就是流量为 v( f ')旳全部可行流中旳最 小费用流.这么,当 f ' 是最大流时,它即为所求旳最小费用最 大流.
cij ,即正向弧集中每一条弧是非饱和弧; cij ,即反向弧集中每一条弧是非零流弧.
四、截集
1 、设 S,T V , S T , 把始点在 S ,终点在 T 中旳全 部弧构成旳集合,记为 (S,T ).
2 、给定网络 D (V , A,C)若点集 V 被剖分为两个非空集合
__
__
__
v1 (2,2)
v2
(3,3)
(4,3)
vs
(0,)
(1,0) (1,0)
(5,2) v1 (vs ,3) (2,2)
v4
(5,3)
(3,0)
vt
(2,2)
v3
v4 (5,3) vt
(3,0) (2,2)

(10,7)
v1
(7,7) (2,0)
vs
(8,4)
(5,0)
vt
(4,4)
v2
(10,4)
v3
(未标费用)
最大流图fmax=11
(10,4)
v1
第1次迭代
(7,1)
(2,6) (10,4,0)
v1
(7,1,5) (2,6,0)
vs (5,2)
(8,1)
vt
(4,2)
vs (5,2,5)
(8,1,5)
min{15 4, 7 0,11 0} 7
④得到新的可行流，刷新网络图 v2
(3,3,0) (7,8, 7) (4,9, 4)
f 17 f max 20
(15, 2,11)
v4
(11,3, 7)
vs
(9, 6, 6)
(bij , cij , 0)
Vi
原网络
Vj
(bij , cij )
Vi
增广费用网络
Vj
非饱和弧上 (0 xij bij ) ，原有弧以单位 费用作权数，后加弧（虚线弧）以单位 费用的负数作权数：
(bij ,cij , xij ) (bij xij , cij )
( xij ,cij )
第五节 最小费用最大流问题
一、基本概念
1、什么是最小费用最大流问题？
对每一条弧都给出单位流量费用的容量网络 D=（V，A，B）（称为费用容量网络）中， 求取最大流X，使输送流量的总费用
C（X）=∑cijxij为最小的一类优化问题。
其中，bij表示弧（vi，vj）上的容量，xij表 示弧（vi，vj）上的流量，cij表示弧（vi，vj） 上通过单位流量所花费的费用。

v2
v3
即是f(1)的最小费用增广链。
第3次迭代
-4 4
v1
-2
-1
(10, 2)
v1
(7, 7) (2, 0)
vs
-1
1
6
2
vt
(8, 8)
vs
(5, 5)
vt
(4, 3)
v2
3
v3
①零流弧保持原边，非饱和非 零流弧增添后向弧，饱和弧去 掉原边增添后向弧
(10, 3) ①流量调整量ε3=min{85,10-0,4-0}=3， 总流量v(f(3)) =原流量+新 增流量=7+3=10； ②最小费用增广链的费用 ∑bij=1+3+2=6
链中费用最小的增广链，那么沿着
f μ去调整 f 得到的新的可行流
v (f ) 就是流量为
的最小费用流。
（2）实现思路
基于第一种求解途径，根据上述定理， 从流量为v(f) 的最小费用流f 开始，只要找 到其上的最小费用增广链，在该链上调整流
量，就得到增加流量后的最小费用流。循环
往复就可以求出最小费用最大流。 实施中的关键——寻找最小费用增广链 具体方法：构造增广费用网络图，借助最短路 算法寻找最小费用增广链。
-4
v1
6 2 3 -3
-1
vs
-1
4 -2
vt v3
-2
v2
vs v1 v2 v3 vs 0 4
vt d(1) d(2) d(3) d(4) 0 0 0 0
v1
v2
-4
-1
0
2
-2
0
6
3
4
4
2
4

该算法基于Ford-Fulkerson方法和增广路径的概念，通过不断寻找增广路径并更 新流，最终得到最大流。
预处理步骤
初始化
为每个节点和边设置相应的容量和费 用。
残量网络构建
寻找增广路径
在残量网络中寻找增广路径，即从源 点到汇点存在一条路径，该路径上的 所有边都未满载且具有正的残量。
根据边的容量和费用，构建残量网络。
05
算法的复杂度和优化
时间复杂度分析
算法时间复杂度
最小费用最大流问题通常使用Ford-Fulkerson算法或其变种来解决，时间复杂度为O(V^3 * E)，其中V是 顶点数，E是边数。
优化策略
为了提高算法效率，可以采用预处理、动态规划、记忆化搜索等策略，减少不必要的计算和重复计算 。
空间复杂度分析
最小费用最大流问题可以应用于多种 实际场景，如物流运输、能源分配、 通信网络等。
背景和重要性
最小费用最大流问题作为网络流问题 的一个重要分支，在计算机科学、运 筹学和工程领域具有广泛的应用价值。
解决最小费用最大流问题有助于优化 资源配置、降低成本和提高效率，对 于实际问题的解决具有重要的意义。
02
此外，随着计算科学和数据科学的快速发展，如 何利用新的技术和方法来求解最小费用最大流问 题也是值得关注的方向。
例如，如何设计更高效的算法来求解大规模的最 小费用最大流问题？如何处理具有特殊性质的最 小费用最大流问题？如何将最小费用最大流问题 的思想和方法应用到其他领域？
因此，未来对于最小费用最大流问题的研究仍具 有广阔的空间和挑战性。
案例一：简单网络流问题
问题描述
给定一个有向图G(V,E)，其中V是顶点的集合， E是边的集合。每条边(u,v)有一个非负的容量 c(u,v)和一个非负的费用f(u,v)。求从源点s到 汇点t的最大流，使得流的总费用最小。