米特号类似网站,品牌建设实施方案,网站开发 多语言,网站想上线怎么做文章目录 流网路残留网络增广路径割最大流最小割定理最大流Edmonds-Karp 算法算法步骤程序代码时间复杂度 流网路
流网络#xff1a; G ( V , E ) G (V, E) G(V,E) 有向图#xff0c;不考虑反向边s#xff1a;源点t#xff1a;汇点 c ( u , v ) c(u, v) c(u,v)#xff… 文章目录 流网路残留网络增广路径割最大流最小割定理最大流Edmonds-Karp 算法算法步骤程序代码时间复杂度 流网路
流网络 G ( V , E ) G (V, E) G(V,E) 有向图不考虑反向边s源点t汇点 c ( u , v ) c(u, v) c(u,v)边的最大容量可行流 f f f 容量限制 0 ≤ f ( u , v ) ≤ c ( u , v ) 0 \leq f(u, v) \leq c(u, v) 0≤f(u,v)≤c(u,v)流量守恒除了源点和汇点所有点满足 流入 流出 流入 流出 流入流出 ∣ f ∣ |f| ∣f∣可行流的流量即从源点流向汇点的速率。一种通用的解释是 从源点流出的流量 − 流入源点的流量 从源点流出的流量 - 流入源点的流量 从源点流出的流量−流入源点的流量最大流最大可行流
残留网络
残留网络定义一个可行流流网络 f f f 对应一个残留网络 G f G_f Gf
点集与原图的点集一样 V f V V_f V VfV边集不仅包含原图的边同时包含所有边的方向边即 E f E 和 E 中的所有反向边 E_f E 和 E中的所有反向边 EfE和E中的所有反向边边的容量 c f ( u , v ) c_f(u, v) cf(u,v) 原图中的边剩下的容量即 c ( u , v ) − f ( u , v ) c(u, v) - f(u, v) c(u,v)−f(u,v)反向边可以退回的流量即 f ( v , u ) f(v, u) f(v,u)
重要结论原网络的可行流 f f f 加上可行流对应的残留网络 G f G_f Gf也是一个可行流
对应边相加若方向同则相加若反向反则相减结论 ∣ f f ′ ∣ ∣ f ∣ ∣ f ′ ∣ |f f| |f| |f| ∣ff′∣∣f∣∣f′∣进一步若残留网络没有可行流那么原网络的可行流就一定是最大流
增广路径
在残留网络里如果沿着容量大于 0 的边走能走到汇点则这条路径叫做增广路径
若存在一个增广路径根据 ∣ f f ′ ∣ ∣ f ∣ ∣ f ′ ∣ |f f| |f| |f| ∣ff′∣∣f∣∣f′∣原来的可行流一定不是最大流若不存在增广路径我们可以得出当前可行流就是最大流
割
将点集 V 分成 S 和 T 两个子集
分割要满足 S ∪ T V S ∩ T ∅ S ∪ T V S ∩ T \emptyset S∪TVS∩T∅点集不一定连通
割的容量 c ( S , T ) ∑ u ∈ S ∑ v ∈ T c ( u , v ) c(S, T) \sum_{u ∈ S} \sum_{v ∈ T} c(u, v) c(S,T)∑u∈S∑v∈Tc(u,v)
最小割最小割的容量割的容量不考虑反向边
割的流量 f ( S , T ) ∑ u ∈ S ∑ v ∈ T f ( u , v ) − ∑ u ∈ T ∑ v ∈ S f ( u , v ) f(S, T) \sum_{u ∈ S} \sum_{v ∈ T} f(u, v) - \sum_{u ∈ T} \sum_{v ∈ S} f(u, v) f(S,T)∑u∈S∑v∈Tf(u,v)−∑u∈T∑v∈Sf(u,v)
流过去的流量减去流过来的流量割的流量考虑反向边
重要性质 对于任意一个割割的流量一定小于等于割的容量即 f ( S , T ) ≤ c ( S , T ) f(S, T) \leq c(S, T) f(S,T)≤c(S,T) 割的流量等于原流网络的流量即 f ( S , T ) ∣ f ∣ f(S,T) |f| f(S,T)∣f∣ f ( X , Y ) − f ( Y , X ) f(X, Y) -f(Y, X) f(X,Y)−f(Y,X) f ( Z , X ∪ Y ) f ( Z , X ) f ( Z , Y ) f(Z, X ∪ Y) f(Z, X) f(Z, Y) f(Z,X∪Y)f(Z,X)f(Z,Y) f ( X ∪ Y , Z ) f ( X , Z ) f ( Y , Z ) f(X ∪ Y, Z) f(X, Z) f(Y, Z) f(X∪Y,Z)f(X,Z)f(Y,Z)
最大流最小割定理 以下三个条件是等价的 可行流 f f f 是最大流可行流 f f f 的残留网络中不存在增广路存在某个割 [ S , T ] [S, T] [S,T] ∣ f ∣ c ( S , T ) |f| c(S, T) ∣f∣c(S,T)
最大流
Edmonds-Karp 算法
算法步骤
维护流网络的残留网络不断进行以下流程
找一条增广路 f ′ f f′可以用 BFS 进行搜索更新残留网络 G f → G f f ′ G_f → G_{f f} Gf→Gff′
程序代码
#include iostream
#include algorithm
#include cstringusing namespace std;const int N 1010, M 20020, INF 1e8;// 邻接表存储残留网络
// 正向边和反向边成对存在正向边的下标异或上1得到方向边的下标
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx; // f表示容量
int q[N], d[N], pre[N];
bool st[N]; // 避免重复搜索void add(int a, int b, int c)
{// 正向边 e[idx] b, f[idx] c, ne[idx] h[a], h[a] idx;// 反向边初始容量为0e[idx] a, f[idx] 0, ne[idx] h[b], h[b] idx;
}// bfs找增广路
bool bfs()
{int hh 0, tt 0;memset(st, false, sizeof(st));q[0] S, st[S] true, d[S] INF;while(hh tt) {// 从队列中弹出一个元素进行BFSint t q[hh];for(int i h[t]; ~i; i ne[i]) {// 节点t的临接边i的下一节点verint ver e[i];// 没遍历过且边i的容量不为0if( !st[ver] f[i] ) {st[ver] true;// 流到节点ver的流量为流到t的流量和边i容量的最小值d[ver] min(d[t], f[i]);// 记录节点ver前驱边的编号pre[ver] i;if(ver T) return true;// ver入队q[tt] ver;}}}return false;
}// EK 算法
int EK()
{int r 0;while( bfs() ) {// 加上增广路的流量r d[T];// 更新残留网络for(int i T; i ! S; i e[pre[i] ^ 1]) {// 正向边更新f[pre[i]] - d[T];// 反向边更新f[pre[i] ^ 1] d[T];}}return r;
}int main()
{// 点数、边数、源点、汇点cin n m S T;// 初始化邻接表memset(h, -1, sizeof(h));while( m-- ) {int a, b, c;// 边ab的容量为ccin a b c;add(a, b, c);}cout EK() endl;return 0;
}时间复杂度 O ( V E 2 ) O(VE^2) O(VE2)
