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

基于网络流
网络流的基本知识及其求解
网络流量在OI中尤为重要。在《算法导论》中，有35页专门讲述网络流的知识。在这里，我给大家讲一些网络流量的基础知识。
如果互联网流媒体很难，那你就大错特错了。建议你学完最短路径，最小生成树或者LCA，Tarjan之后可以看一看。一般的普及群体都能消化。
流动
首先，我们要知道什么是流量。我们知道，我们城市的每一条道路都必须有一定的宽度，而这些宽度限制了车辆。(我们也可以把红绿灯的两端看成一条路的长度。)
网络流用这样的值解释图形，这与最短路径不同。a站到哔哩哔哩有一条路，车流量
5，只能通过5辆车(或者其他单位)，过了就过不去了。我们还可以推出一些东西:
一、我们可以先接N辆车，再接M辆车。(n+m & lt；=这条路的流量)
二。如果从站A到哔哩哔哩只有20的流量，那么我们有一条流量为15的边来连接B和C..我们很快就能引入从A到c只有15的流量(因为后者限制了前者)
最大流量
先了解S(源)和T(汇)的概念。s就是常说的源点，T就是汇点(也就是起点和关键点，和最短路径概念一样) 。我们有一个图，要求从源头到汇点的最大流量(可以有多条路到达汇点)，这就是我们的最大流量问题。(一般源点不限流量)
【oi缩写代表啥意思网络中的oi是什么意思】那么我们来了解一下增广路(注意路不是边)，也就是从源点到汇点，只要有流量(flow >；0)流过去，这条路就是增广路。在一些最大流算法中，这些路径是增广的(意思是从这条路径走掉，走掉的流量一定是这条路径的最小流量)，如图:

文章插图
文章插图
从4到3，肯定可以从流量为20的一侧先走。则该边已被移除，并且不能再次被选择。总流量20(现在) 。那么我们可以这样选择:
一. 4->2->；这条扩建道路的总流量为20 。2点还是30，3点才20 。
二。4->；2->；1->；这样才能很好的保持30的流量。
所以我们图的最大流量应该是20+30=50 。
求最大流很简单，后面我们会讲解三种求最大流的方法。
最小成本最大流量(MCMF)
这也是众所周知的成本流——最小成本最大流。我们给这个图一个成本值(也就是最短路径问题)，然后在求最大流的基础上，求最小成本的路径。这个难度上升到了群体提升的难度，并不是每个人都具备的先决条件。(不过还是很简单)
最大流解决方案的集合
代码(全部)请看:剪贴板(https://www . luogu . org/paste/6t 8 jgtxc) 。
埃德蒙-卡普动能算法(EK算法)
这个算法很简单，就是Dfs找到增广路径，然后增广。你可能会问，怎么找？怎么拓宽？
一.找什么？我们只是从源头点走到Dfs，停在汇合点，然后拓宽(每条路都要拓宽) 。我们在Dfs的时候，只要关注流量是否合法就可以了。
二。增强？其实就是按照我们要找的增广路再走一遍。走的时候，减去这条路的最小流量，再加上最小流量的答案。
再来说说反边。增广的时候要注意反向边的构造，因为这个路径不一定是最优的，这样子程序就可以反悔。如果我们延伸这条路，那么每一边的对面的流量就是它的流量。
说一些小细节吧。如果用邻接矩阵，反边直接从表[x，y]变成表[y，x] 。如果是常用的链正向星，那么加边的时候要先加反向边。所以当我们使用它的时候，我们可以直接I xor 1(I是边的数目) 。为什么？相信大家对xor都有所了解，所以我们可以通过在正向边沿后面加上反向边沿来使用xor，也就是接近。我们还应该注意，初始数字应该设置为tot=1，因为边应该以数字2开始，这样xor将对编号为2和3的边产生影响。

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

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