上下界网络流

摘要

对于普通的网络流问题,我们在一个网络 上求解相关的问题。网络的边有一个容量,即流量上界 。而有时候我们要求这条边有一个流量下界 ,这样的相关问题被归为上下界网络流问题。

无源汇可行流

对于没有源点,汇点的一个上下界网络,我们想要求解其中的一个可行流。即判断是否存在合法的流。形式化的问题如下

给定一个无源点汇点的网络 ,每条边 有一个流量上界 和流量下界 。要求每个点满足流守恒性,判断是否有解,并求一组可行解。

首先,一个直观的想法是添加一个超级源点s和超级汇点t。


  转载请注明: Sshwy's Blog 上下界网络流

 上一篇
扩展埃氏筛 扩展埃氏筛
摘要 本文介绍一种比欧拉筛更高效的筛法,扩展 Eratosthenes 筛法。 杜教筛适用范围较小,未充分利用积性。扩展埃氏筛要求对于任意质数 p, 是一个关于 p 的低阶多项式。对于任意 的指数
2019.07.13 Sshwy
下一篇 
Prufer 序列 Prufer 序列
摘要 本文翻译自 e-maxx Prufer Code,兹瓷一下OI-WIKI的计划。另外解释一下,原文的结点是从 0 开始标号的,本文我按照大多数人的习惯改成了从 1 标号。 这篇文章介绍 Prufer 序列 (Prufer code)
2019.07.07
  目录