网络流常用示意图及基本概念

【网络流简介】● 网络流基本概念网络网络是一个有向有权图包含一个源点和一个汇点没有反平行边。网络流是定义在网络边集上的一个非负函数表示边上的流量。网络最大流在满足容量约束和流量守恒的前提下在流网络中找到一个净输出最大的网络流。可行流容量约束、流量守恒。● 网络流常用示意图在残量网络中找可增广路在实流网络中沿可增广路增流在残量网络中沿可增广路减流。增广路定理设 flow 是网络 G 的一个可行流如果不存在从源点 s 到汇点 t 关于 flow 的可增广路p则 flow 是 G 的一个最大流。● 利用“^1”运算表示反向边由于网络流是有向有权图因此可以选择链式前向星存图。对一个数连续执行两次“^1”运算后便会得到自身。这恰好与网络流中“反向边的反向边等于自身”不谋而合。因此在网络流的算法实现中我们可以利用“^1”运算来表示反向边。● 链式前向星https://blog.csdn.net/hnjzsyjyj/article/details/139369904val[idx]存储序号为 idx 的边的值e[idx]存储序号为 idx 的结点的编号ne[idx]存储序号为 idx 的结点指向的结点的编号h[a]存储头结点 a 指向的结点的编号