上下界网络流概念每条边有个流量限制\([l,r]\)，要求该边流量\(f\)满足\(l\ler\ler\)无源汇上下界可行流可以强行每条边先流\(l_i\)，再将将边设为\(r_i-l_i\)，但是我们发现每个点的流量不平衡，于是设\(w\)为入流流量-出流流量\(w>0\)时，让\(s'\)向\(i\)连流量为

顾名思义，有上下界的网络流与一般网络流相比多一个下界的限制，就是一条边的流量要满足在\([l,r]\)这个区间内。这里一共有三个问题：1.无源汇有上下界可行流2.有源汇有上下界可行流3.有源汇有上下界最大/小流三个问题是前后关联的。无源汇有上下界可行流对于一条边\(u\tov\)，定

  前情提要：在「洛谷P8477」「GLR-R3」春分中，我们给出了\(\frac{7}{6}n\pm\mathcalO(1)\)的解法，但没能给出相关的下界证明。现在我们尝试给出一个未完全完成的下界证明。  为方便描述，我们综合链接中题意和某个“通俗”的题意，称隔板为“板”，称溶液为“人”。  这个

排列\[A_n^m=\dfrac{n!}{(n-m)!}\]组合\[\dbinom{n}{m}=\dfrac{n!}{(n-m)!}\]下降幂&上升幂\[\]二项式定理隔板法如果隔板法的每个间隔有下界（下界可以不同），可以先把下界从整体减去。P5520[yLOI2019]青原樱：可将树看作隔板。环排列\(n\)的长度，\(m\)种颜色。可以

转化成差分之后，差分数组里面正数的和一定不会小于负数的和的绝对值（因为\(h_i>0\)），所以答案的下界是正数的和我们来证明一定存在一种方案达到下界用数学归纳法。设差分数组为\(d\)显然\(d_1≥0\)；也有\(d_1+d_2≥0\)（假设\(d_2\)为负），也就是说，我们可以通过先操作\(d_1\)和\(d_2\)来

哎，就差一个考虑上下界啊！来看看官解首先一个连通块的大小不可能超过\(k\)，比较显然当\(n>k\)的时候，我们将点连续的分成\(\lceil\frac{n}{k}\rceil\)个，然后考虑\(n=k\)的情形官解是这么分权值的其实我考试的时候想出来这个的，手搓几次样例就可以发现了。。但是我却没有利用上

由于只需要考虑相邻的位置，所以每一段连续的F是互不影响的，可以分别进行考虑。而连续的一段F又可以分成两类：靠边的和被夹在中间的。靠边的F段较为简单，假定有\(c\)个F，不难发现只要让EB交错出现就可以达到最少次数，而让所有的F都变成最近的非F就可以达到最多次数\(c

为什么有人联考放论文题啊？不过好有趣。参考的glx博客。考虑这么一个问题，给定一张偏序图，即一个满足传递性和非自反性的偏序关系\(\succ\)连成的DAG。你需要对这张图进行拓扑排序，每次可以同时删去一个或者两个零入度点，问最少删多少次可以把图删空并构造方案。形式化地说，我们

Describe:\(n\)个点，\(m\)条边，每条边\(e\)有一个流量下界\(\text{lower}(e)\)和流量上界\(\text{upper}(e)\)，求一种可行方案满足流量守恒的同时满足每条边的限制条件。Solution:可以先考虑满足所有边的最低条件，获得一个初始的流量网络。这时各个点是不一定满足流量守恒

最大流/最小费用最大流这里不再讨论，使用Dinic即可。板子是可以感性理解然后背下来的。无源汇上下界可行流随便来一张网络，边上的流量有上下界，求一种所有点都满足流量平衡和上下界限制的方案。首先有一个想法是把上下界转换成只有上界，那么为了清除下界的障碍，我们就先把所有边

对网络的定义进行扩展，我们可以得出一堆奇奇怪怪的网络。上下界令\(Max_e\)为边\(e\)的流量上界，\(Min_e\)为边\(e\)的流量下界，一条边的流量\(f_e\)要满足\(Min_e\lef_e\leMax_e\)，除此之外和普通网络流定义相同，可以发现，普通的网络就是下界为\(0\)的网络。无源汇

公众号：编程驿站1.搜索算法本文和大家聊聊搜索算法，计算机解决问题的抽象流程是，先搜索，或完全搜索后得到答案，或边搜索边找答案。所以，对给定的数据集进行搜索是解决问题的前置条件。不搜索，无问题。搜索算法无非就是线性、二分、深度、广度搜索算法。其它的搜索算法的底层逻辑也是建

\(\newcommand{\NP}{\mathsf{NP}}\newcommand{\PP}{\mathsf{P}}\newcommand{\PPoly}{\mathsf{P/_{poly}}}\newcommand{\EXPSPACE}{\mathsf{EXPSPACE}}\newcommand{\SigmaTwo}{\mathsf{\Sigma_2}}\newcommand{\E}{\mathsf{E}}\newcommand{\F

CF1894D退役之后啥也不会了/kk首先容易想到\(b_i\)递减插入更优。考虑答案的下界显然是\(LCA(a)\)，答案的上界为\(LCA(a)+1\)，因为我们总是可以在任意位置插入递减的\(b_i\)来得到。因此我们只需要考虑怎么判断当前答案取上界还是下界即可。实际上，答案的下界是始终

首先，\(max(p,q)\)是下界，因为连一条边最多只能减少一个零入度点和一个零出度点，而最终的图不可能有哪怕一个零出度点或者零入度点（最后的图刚好就是一个点）根据这个下界，我们也很容易可以构造出来一种方法，让零出度点和另一个SCC的零入度点相连即可，就像下面一样（红色边是添加的边）

学一次忘一次，搞笑。规定\(s\)和\(t\)为原图的源汇点，\(S\)和\(T\)为新建的虚拟源汇点。无源汇上下界可行流考虑先把每条边的下界流满，然后网络的边权改为\(r-l\)。但这样每个点的流量平衡不能保证，我们建源点\(S\)和汇点\(T\)，如果一个点的入量大于出量，就从\(S\)到它

最小费用循环流考虑如果费用全部是正的，那么最小费用一定是0.可以强制把所有负边流满，留下反悔边。如果一个点出度大于入度，那么这个点向虚拟汇点连出度减入度，否则从虚拟源点向这个点连入度减出度。无源汇上下界可行流先强制把下界流满，统计每个点的流出和流入。如果流出比流入多

四、用go语言，假设现有一个包含n个元素的待排序序列。该序列由n/k个子序列组成，每个子序列包含k个元素。一个给定子序列中的每个元素都小于其后继子序列中的所有元素，且大于其前驱子序列中的每个元素。因此，对于这个长度为n的序列的排序转化为对n/k个序列中的k个元素的排序。试证

四、用go语言，假设现有一个包含n个元素的待排序序列。该序列由n/k个子序列组成，每个子序列包含k个元素。一个给定子序列中的每个元素都小于其后继子序列中的所有元素，且大于其前驱子序列中的每个元素。因此，对于这个长度为n的序列的排序转化为对n/k个序列中的k个元素的排序。试证

P4843题解原题连接建模一到比较裸的有源汇上下界最小流。每条边必走一次，要求求出最小的流量。由于比较裸，这里当作上下界流的例题讲。什么是有源汇上下界最小流顾名思义，就是在最大流的基础上增加了边的最小经过流量，使得整个网络可行，并且找出最小流量的方案。一个比较朴实的

P3436[POI2006]PRO-ProfessorSzu求scc后变为DAG，随便dp就好了。吐槽数据不对题面，细节巨多。但是肯定不够紫题。P3469[POI2008]BLO-Blockade500年前就做过了，又写了一遍，用了圆方树逃课。就是树上经过每个点的路径数量。P2860[USACO06JAN]RedundantPathsG好题。边

首先这道题\(T\)的范围很小，而\(N\)的范围却很大，所以我们只能枚举树那么我们如何枚举呢，树有上下左右之分，看起来十分难枚举，现在让我们仔细分析一下：水池的边长就等于\(min(上下界的距离，左右界的距离)\)这时我们就可以开始枚举了，我枚举的是左右界那么我们此时就可以发现上下界的两

昨天CF1368H的基础网络流部分我不会，今天noi2019d1t3的网络流我又不会。想当年大家都说我网络流很好来着，现在只需要两个题就足够把我击垮了。于是再来做一些网络流题，或者是一些原来做过的题的回顾，以此总结一些经验。流量限制的是最大值而非最小值，故当限制为最小值时考虑转化

一、概述Ο，读音：big-oh；表示上界，小于等于。Ω，读音：bigomega、欧米伽；表示下界，大于等于。Θ，读音：theta、西塔；既是上界也是下界，称为确界，等于。ο，读音：small-oh；表示上界，小于。ω，读音：smallomega；表示下界，大于。Ο是渐进上界，Ω是渐进下界。Θ需同时满足大Ο和Ω，故称为确界。Ο极其有用，

1.二分查找法用一数组P【i】记录每个位置之前到自己本身位置i有多少个0，只要满足【下界，上界】之间的0个数小于等于k就可以连接成为连续的1。即P【上界】-P【下界】<=k因为第一个位置要是为0要做特殊处理[上界，下界]之间0的个数不能简单用P[上界]-P【下界】,记有n个元素，从P[0]~P