埃德蒙兹-卡普算法
计算机科学中，埃德蒙兹-卡普算法（）通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为O(VE^2)。该算法由在1970年最先提出，并由和理查德·卡普在1972年独立发表。 C++實作 以下是关于埃德蒙兹-卡普算法的C++语言描述： struct Main { struct Edge { int u, v, Capacity, Flow; Edge (int u, int v, int Capacity, int Flow)…
标签：#网络流
共 3 篇文章
最小割
在图论中，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的割（），一张图上最小的割称为最小割（或）。与最小割相关的问题称最小割问题（或），其变体包括带边权、有向图、包含源点与汇点（简称有源汇），以及将原网络分为多于两个子图等问题。其中，带边权的最小割问题允许有负权边，可通过对所有边权取相反数简单地转化为最大流问题求解。 无源汇的最小割问题 对于带有边权的无向图，其最小割问题可以在多项式时间内通过求解。在无边权的特殊…
最小费用最大流问题
最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求。 问题提出 有足够多辆卡车要将数量无限的某种物品从一个地点运输到另外一个地点，现在有有限条单向行驶道路直接或者间接地连接了这两地。但是每一条道路都有运输通过总数量的限制，称为容量，同时携带物品通过该路段时，都会按照携带物品数…