oi缩写代表啥意思网络中的oi是什么意思( 二 ) _生活百科

迪尼奇
我们可以来尝尝迪尼奇的http://www.tommydinics.com 。这是我找到的唯一解决办法。
好吧，开个玩笑，我们学Dinic吧。我们知道一次找到一条路是很慢的，所以我们会想象是否可以一起找到很多条路。答案当然是肯定的。我们只需要一个问题。这些道路是同时发现的。如果有的路调皮回头(其他路)，那么其他路就不是很尴尬了。
如果我们给这张图的每条边指定一个方向，就不会出现上述情况。然后才能知道分层的概念。我们在每次增强后对图表进行分层。我们规定低层次只能去高层次(而且只能高一个层次) 。水平面是它离源点的距离。我们只需要一个BFS用于每次整体增强。
ISAP
这是SAP算法的改进版本。我建议去看看https://www.cnblogs.com/owenyu/p/6852664.html’s的博客或者我的。这里不做解释。
最小成本最大流量(MCMF)解决方案
好吧，我承认我只知道EK+SPFA，直接看代码。很简单，网络流量设置一套SPFA 。我相信世界上能摆脱EK+SPFA的人不多(但有很多) 。
这里推荐原对偶算法(网上说的人不多)和zkw成本流算法(zkw太强了！) 。博主们正在学习。
网络流的基础知识扩展
了解前面一切的同学可以看看下面。
最小切割
其实切割就是删边。当然，最小割是指割开X条边，使S和T互不相通。我们要求X边的组合流量最小。这是最小割问题。
其中要知道一个定理:最小割=最大流(虽然我不会证明)
埃尔芬图皮佩
这个特别简单，可以用匈牙利水法。这里不多说，参考我的博客(https://www . luogu . org/blog/ack ing/solution-p 3386) 。
制作模型
在了解了最大流和费用流之后，建模就显得尤为重要。就像JZOI的《狼与羊的故事》(https://www . luogu . org/problem new/show/p 2598)就是一个例子。
前期遇到这种问题，我暴力搜？魔术师BFS？错误。首先要考虑是否会有二部匹配的最小割模型(一般不会有普通的最大流) 。然后建立(超级)源点和(超级)汇点。你什么意思？即在源点多汇点多的情况下，我们可以用超级源点和超级汇点代替“源点”和“汇点”的位置(即超级源点连接源点，超级汇点连接汇点，具体看问题的意思) 。
这是最常见的建模方法之一，也是做二分匹配的方式。建模方法很多，等你自己去研究。这里有一个很好的博客供你自己学习。
用一个问题练手:t 。
这篇文章由arfa发表在《洛古日报》上。
原地址:https://www.luogu.org/blog/acking/network-flows-ji-chu

oi缩写代表啥意思 网络中的oi是什么意思( 二 )

oi缩写代表啥意思网络中的oi是什么意思( 二 )