“最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。”这样的定义可以让你理解算法执行的逻辑，却难以在你赛场上遇到它时牵动你的思绪更符合你做题时真切感受的描述应该是：给你一些点，消耗一些

原来我没学过图论。尝试把普及组+提高组的大部分图论内容重学。定义啥的不写了。OI-Wiki有详细的。图的存储一般来说有3种存图方法：直接存。例如structEdge{inta,b,w;}edges[N];。邻接矩阵。即一个矩阵\(g\)，其中\(g_{i,j}\)表示\(i,j\)间的边数。如果

9.1arc108e当已经选了\(a_l,a_r\)时，\((l,r)\)与外面无关。区间dp，\(dp_{l,r}=\frac{\sum_{k=l,a_l<a_k<a_r}^rdp_{l,k}+dp_{k,r}}{num_{l,r}}+1\)。维护\(num_{l,r},\sumdp_{l,k},\sumdp_{k,r}\)转移。9.2P5188模拟赛T2。容斥强行不选\(s\)这些材料，矩阵快速幂。

对于题目给的图\(G\)，我们添加一条边\((t,s)\)转化成\(G_1\)，对\(G_1\)求无源汇上下界可行流，添加虚拟源汇点\(S,T\)得到的图是\(G_2\)，对\(G_2\)跑dinic，此时得到的最大流\(f\)满足\(S\)的每条出边都是满的，\(T\)的每条入边都是满的，\(f\)诱导出的\(G_2\)的残存网络为\(G_3\)，在\(G_3\)中

模拟费用流是什么考虑一般的单路增广费用流流程，就是一直去寻找最小/最大费用增广路的过程。但是寻找一条增广路往往需要最短路算法，这造成了很大的时间开销。找到增广路的方式不唯一，可以通过别的手段去寻找增广路。在一些特殊网络中可以获得更加优秀的时间复杂度。QOJ7185题目

网络流网络流初探A.【例题1】求最大流P3376模板。B.卖猪问题SP4063&&P4638Solution[trick]：网络流有时间顺序要求的考虑分层图，优化建图的思路很妙。D.危桥通行P3163Solution正常按照题意建边，危桥建边权为\(1\)的双向边，普通的桥建边权为\(inf\)的双向边，源点向

A-GoingHomeHDU1533GoingHome题解：费用流板子题，没什么好说的B-BoxesSOPJBoxes题解：又一道费用流板子题，但是我以为它是个序列然而它是个环C-TheMostRecklessDefenseTheMostRecklessDefenseCF1955H题解：省流，写了篇题解：为什么所有题解都是状压DP，这题不是看

2023.5做题记录[Violet]天使玩偶显然发现我们需要在时间轴上进行cdq分治，然后统计答案。问题在于这个绝对值不好维护，需要进行转化。如果我们钦定这个点最近的点在它的左下方，那么绝对值就可以化为\(dis(A,B)=(A_x-B_x)+(A_y-B_y)=(A_x+A_y)-(B_x+B_y)\)。显然前面的括号是定

1.概述网络指的是一类特殊的有向图G=(V,E)，与一般有向图不同的是有容量和源汇点对于网络G=(V,E)，流是一个从边集E到整数集或实数集的函数，满足如下性质容量限制：对于每条边，该边流经的流量不得超过该边的容量流守恒性：除源汇点外，其余任何点的净流量为0，其中，我们定义节点u的净流

前言Classtakenon4.2Writtenon4.29Flow解决问题类网络流是用有向图每条边来模拟流动，有流量限制的情况下，求解最大流量（有时以及最小费用）的问题。同时也是将各类问题（尤其匹配问题）通过建模为网络流来用网络流算法求解的一个方法。解决问题的一般特点：数据范围不大不小，\(

网络流的建图灵活，需要大量练习。一些常见套路：拆点：一般来说可以把一个点拆为一个入点和一个出点并连边，用于点边转化。连INF边：这种边不可能包含在最小割中，可以用来将点定向。建立超级源点和超级汇点：用于构建网络流模型。加辅助点：比较灵活，可以用于处理多种问题。做

1.1.3.4最小割之建图实战、费用流基本概念最小割之建图实战381.有线电视网络Problem给定一张n个点m条边的无向图，求最少去掉多少个点，可以使图不连通。如果不管去掉多少个点，都无法使原图不连通，则直接返回n。Solution最小割模型的通用分析方式：通过原图构造一个流网络

A是谁瞪了半个小时不会*2000呀，是谁呀是谁呀。感觉这题比部分紫题都难。。。首先发现选取字符的顺序并不重要，所以\(t\)可以看成\(26\)个字符要选的个数。设字符\(c\)出现了\(x\)次，那么直接向汇点连流量为\(x\)费用为\(0\)的边。然后考虑\(s_i\)与每个字符的关

Describe:\(n\)个点，\(m\)条边，每条边\(e\)有一个流量下界\(\text{lower}(e)\)和流量上界\(\text{upper}(e)\)，给定源点\(s\)与汇点\(t\)，求源点到汇点的最小流。Solution：首先因为仍然有流量的限制，第一步就是要找可行流。想到上题无源汇做法，尝试转换。上题中可行流实际

【什么是网络流】一张带权图，给定了一个源点（起点）和一个汇点（终点）。每个点比作一个中转站，源点比作一个水源，汇点比作一个洞。每条边比作一条管道，边权比作上限。现在要把水从源点输送到汇点，水经过若干中转站和管道到达汇点。但是，每条管道单位时间内输送的水不能达到这条管道的上

当学习笔记用，持续更新。写给自己看的，图有点少。如果有人真想通过这篇博客学网络流的话也不是不行……因为更新极慢无比，所以这篇博客里的各份代码码风可能会出现巨大的差别。关于学习途径显然有无数人在自学网络流的时候因为网上大部分题解的姿势都过于抽象而被劝退，所以提一下

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

K8这几天不在，原来是每天写3000道题，从一个连深搜都写的对的dalao成长为NOIAKer，创造了NOIP一百九十多省选600分的奇迹，这几天不在已经刷了24000道了我去今天我怎么疯狂被JC，错了哥原来\(K8\)说的二分图不重要说的是可以用网络流代替「重要提醒」：学过网络流后你会发现这玩意很不重

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

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

序幕到校同学都没来，先摆。写博客，写啊，写啊。改费用流板子。\(\color{royalblue}{P3381\【模板】最小费用最大流}\)板子。痛心疾首，建边的时候费用边反边为负权边。\(\text{Link}\)间幕\(1\)水一道平衡树加强版，直接复制粘贴板子，无意义的。网络流。\(\color{royalblue}{P

飞行员配对方案问题二分图最大匹配模板,最大流即可.负载平衡问题显然,当库存比平均数大时,这个仓库就应当向外输送货物;反之,这个仓库就应该接收货物.每一个仓库都要接收货物或输出货物,因此拆成两个点,一个输出,一个接收.当库存比平均值大时,超级源点向该点的输出

T1简单的最短路到终点时不用等红灯，不然会挂40ptT2记\(f(i,j)\)表示跳到\((i,j)\)最少使用的体力。那么转移就是枚举上一个位置然后加上曼哈顿距离求最小值。考虑优化，我们注意到如果转移都在左上的话坐标正负的贡献是固定的,所以可以使用数据结构维护。先按照一维扫描线

问题描述给定一张图，求任意两点的最小割。要求跑\(n\)次最大流。做法暴力需要跑\(n^2\)次最大流，然而这样很浪费，因为求出\(u,v\)两点的最小割以后，我们还获得了至少一种最小割方案，可以通过这一方案获得更多信息。注意到假设通过最小割断开后，\(s,t\)所在集合分别为\(S,T

[ABC307F]Virus2最短路性质题。首先可以发现一个比较朴素的做法是：每天做一次最短路，然后将可以达到的点标记，下次全部作为汇点再做。复杂度爆炸，考虑优化。发现四周都扩展完的点没有用，那么我们只需要维护感染/非感染点的交界的边，每天更新边疆，然后对于新加入的点做最短路径算法