最小费用流

图论专题小结：最小费用最大流算法一，给定流量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.二，网络输出最大流时，求出最小的费用这就是最小费用最大流问题：既要求出最大流，又要求出达到最大流时候的最小费用。

最小费用流算法
最小费用流算法是一种简单的费用流算法，它旨在解决费用流问题，其中边权最小化。

它可以用于解决实际应用中的资源分配问题，表示流程网络（Flow Network）中使用费用
流算法利用边权来最小化流量路线。

最小费用流算法是一种基于增广路径的状态搜索算法。

它主要由两步组成：一是从源结点到汇结点的增广搜索；二是根据找到的增广路径调
整边权。

只要满足三个要求：1. 所有结点都有非负出度；2. 所有边都具有非负权；3.
所有结点都有相同的进入现金流，则最小费用流算法就可以得到最优解。

在最小费用流问题中，要求最小化所有边上的流入和流出时消耗的权重和，考虑到这
些约束，最小费用流算法具有一定的优越性。

首先，最小费用流算法可以在常数时间内完
成寻路，寻路的次数不会太多，其逻辑清晰，容易理解，对于每个结点，只需要搜索到可
达目的地的路径，而不需要考虑搜索路径的可行性。

由于最小费用流算法在查找算法中总
是具有优先权，因此它也可以改善整体优化算法，提供快速和可靠的结果。

最小费用流算法在实际应用中比较广泛，它可以用于解决很多实际问题，包括报价，
补给，物流等。

最小费用流算法可以帮助用户充分利用现有资源、实现最低开销，同时还
保持最大的流动性，从而降低建设成本和管理成本，使企业经营更加高效。

最小流算法是网络流的一种算法，主要用于解决最小费用流问题。

最小费用流问题是在给定一个有向图中，寻找一条从源点s到汇点t的流量最大的流，使得整个流的费用最小。

最小流算法的基本思想是：首先找到一个增广路径，然后沿着这个路径进行增广，直到没有增广路径为止。

在增广路径上，每条边的流量可以增加，费用也随之增加；而在非增广路径上，每条边的流量不能增加，否则就会违反容量限制。

因此，最小流算法的关键在于找到增广路径。

最小流算法的实现可以采用Ford-Fulkerson算法或Edmonds-Karp算法。

Ford-Fulkerson算法的基本思想是：不断寻找增广路径并对其进行增广，直到没有增广路径为止。

Edmonds-Karp 算法则是Ford-Fulkerson算法的一种改进版本，可以更快地找到增广路径。

在实现最小流算法时，需要注意以下几点：
必须判断是否存在可行流，即源点s到汇点t是否存在一条流量大于等于0的路径。

在增广路径上，每条边的流量可以增加，但必须保证不违反容量限制。

在非增广路径上，每条边的流量不能增加，否则就会违反容量限制。

必须记录每条边的当前流量和最小费用，以便后续的增广操作。

必须判断是否还有增广路径存在，否则需要停止增广操作。

最小流算法的时间复杂度取决于找到增广路径的方法。

如果采用BFS（宽度优先搜索）方法，时间复杂度为O(V^2E)，其中V是顶点数，E是边数；如果采用Dijkstra算法或Bellman-Ford 算法，时间复杂度为O(V^3E)。

第4节最小费用流问题现实中的许多问题除了要求流量最大之外,还要求费用最低。

也就是达到最大流量的方案不止一个,还要考虑费用最低的问题。

对于网络N=(V,A,B)上的每条弧(v i,v j)∈A,给定了弧的容量b ij和单位流量的费用c ij(c ij≥0),寻求一个可行流f={x ij}并使其总费用C(f)=c ij x ij达到最小。

求解最小费用流的方法有生成法与调整法两种。

生成法是从零流开始,每次依据最小费用链作为可扩充的路,进行网络流量增大的调整。

调整法只是调整流量的分布,不断改进与改善,使费用减少,寻求最小费用流,但网络流量保持不变。

调整法体现了管理的不断改进与改善哲理,下面以调整法为例,介绍最小费用的求解过程。

一、调整法求解步骤一般求解过程步骤如下:(1)先不考虑费用问题,求得任一可行流f(2)根据这一可行流f构造赋权有向图W(f)。

顶点是原网络N的顶点,弧权根据可行流f 确定。

若弧(v i,v j)的流量可以增加,则照原方向画弧,标上费用c ij,;若弧(v i,v j)的流量可以减少,则照反方向画弧,标上费用-c ij,。

(3)在赋权有向图W(f)中寻找负回路μ。

若没有负回路,则得到最小费用流;若存在负回路,则调整与负回路相对应的弧上的流量,使之费用减少。

(4)根据所得的负回路,比较弧的方向和负回路μ的方向,划分出前向弧和后向弧,计算调整量θ。

θ=min然后,进行流量调整。

若弧(v i,v j)与负回路μ方向一致,则其流量调整为x ij+θ;若弧(v i,v j)与负回路μ方向相反,则其流量调整为x ij-θ。

(5)继续第(2)步,构造赋权有向图,寻找负回路,调整流量,直到没有负回路。

二、调整法应用举例[例6—5]事实上,企业在进行网络流量的调整时,时常要考虑费用问题。

图6—11中弧旁的数字为(b ij,x ij)和c ij。

其中,弧(v s,v1)和(v s,v2)的c s1和c s2分别是两家供应商的货物价格;弧(v5,v t),(v6,v t)和(v7,v t)的c5t,c6t和c7t分别是三个目标市场销售商的售货成本;其余弧(v i,v j)的c ij 为运输、装卸、仓储等物流作业费用。