leoly&diversion的网络流/费用流题单（含其他内容）

时间太少了。 一方面我觉得网络流做这么多就够了，毕竟考得也不多；另一方面又觉得这样的训练根本没有到位。 要是我能够通宵做题状态还不减就好了。~~要是第二天状态还不减就更好了。~~ ## 没有特殊模型 并不代表不难。原本网络流也有这样的题，它们鸽了。 ### $[SDOI2016]$数字配对（zero half） 感觉最近被一些玄学网络流题搞的没有思维了，整个人不正常了。我要冷静冷静。 **** 首先经过观察我们可以发现，将一个数$x$分解质因数，设它的质因数次数和为$f(x)$，那么两个数$x>y$能够匹配当且仅当$f(x)=f(y)+1,y\vert x$。 也就是说，我们可以把$f(x)$按奇偶性分边，然后这样就可以让左右两边匹配，然后就变成了二分图。 那么就这么建，$S\to$左边的点连$\{b_i,0\}$的边，右边$\to T$同理，然后左右匹配的点连容量为$\{+\infty,c_i\times c_j\}$的边。 为了找到最大的满足条件的可行流，我们只能选择贪心地一条一条路增广，每次$SPFA$找到最长路，然后增广之后就看一下当前费用是否$<0$。 **** $UPD:$惊闻$Primal-Dual$能够直接限制流量多路增广，深感震惊。 $UPDD:$惊闻$Dinic$费用流就是原始$-$对偶算法（的弱化版？），深感震惊。 原来$Dinic$也可以做啊$\cdots\cdots$我失了智。 如果当前最长路$>0$显然没有事，如果$<0$并且流量增加$1$都会变成负数就可以直接$break$了。否则直接在$dfs$开始的时候让$flow=cost/-dis[T]$就可以了。$cost$是当前的费用（此处是收益）。 ### $[WF2011]Chips\ Challenge$（half half） 不仅看错题还没想出来，我是弱智。 首先这个题第二个限制是很好解决的，但是也要想清楚这个题答案**并不具有单调性**，也就是说只能**枚举答案而不是二分答案**，然后再通过网络流验证。这个事情不太好说明，但可以脑补一下。于是我们可以枚举零件数量。 然后就可以开始建边了，用**行列建点**的套路拆开，$S\to i$行连一条容量为$[0,\frac{ans\times A}{B}]$的边，$i$列$\to T$连一条同样的边。如果$a_{ij}=.$，就连一条容量为$[0,1]$的边，$=C$就连$[1,1]$，$=/$就不用连。但此时我们并没有解决必须相等的限制。 我们考虑引入费用解决这个问题。首先让第$i$行向第$i$列连$\{+\infty,0\}$的边，然后其它所有点费用都设为$1$。之后我们只要跑最大费用最大流就能够验证答案了。也就是看流量是不是与$ans$相等。 首先我们得弄明白加一条$+\infty$边为什么是正确的。因为第$i$行与第$i$列的与源汇相连边的容量相同，最终第$i$行一定会满流，假设这个流量是$f1$，然后它还给其它点流了$f2$，那么它就通过这条边流了$f1-f2$给第$i$列。又因为第$i$列也满流，那么它为了流量达到$f1$，那也会从其它点拿$f2$流量过来，也就是说它们放的点是一样的，于是就满足了题目限制。 然后我们再想清楚为什么要用到费用。此处之所以要求最大费用最大流，是因为我们添加了一条$+\infty$边，而这条边只是为了满足限制，它上面的流量与题目的限制**并没有任何关系**。也正是因为如此，为了找到真正的合法流量，我们让每条代表安排零件的边都带上一个$1$的费用，而让无穷边的费用变成$0$，在这样的情况下求最大费用最大流就能够保证在满流的情况下尽可能多地安排零件上去，所以判答案的时候我们实际上用的是$cost$而不是$flow$。 还有个**小技巧**：为了减少码量避免上下界费用流，我们可以给所有$=C$的边的费用**加**一个很大的数$x(>n^2)$，最后看最大费用最大流的结果中是否有这么多个$x$，如果这都没有，那显然是不合法的答案。当然为了方便加的这个数最好是$10000$的倍数~~，比如$\sout{10000}$（雾）~~。 ## 路径覆盖 $DAG$路径覆盖内容可参考$Tascho\ 3.$ ### [网络流24题]魔术球问题（half full） 第三遍做这道题了吧。 枚举答案，然后能满足完全平方数的点连有向边，小连大，因为小先放。 显然这是个$DAG$，一个柱子代表一条路径，那么问题转化为$DAG$最小路径覆盖。 直接建模求解即可。只要答案$\le$柱子数就可以继续枚举。 ### $[CTSC2008]$祭祀（zero half） 网络流全忘光.jpg 首先它问的是最多的不可达的点，那就是最长反链。 直接转化为最小链覆盖。 好像有个第二问是问哪些点一定在最长反链上，$leoly$给出的做法是枚举每个点，将可比的点都断掉再求一次。不是很清楚。 ### $[TJOI2015]$组合数学（zero half） 对没错这是最小链覆盖啦。 可是我不知道一个点走多次怎么做啊.gif 转化成最长反链怎么就可以直接把次数当权值了啊？？？ 如果这个成立的话，然后就是一个显然的$DP$~~，我还想错了一点~~。 把$(1,1),(n,m)$设成左上角和右下角，那么因为要不可比，所以就是从右上方转移过来，或者这个点不选转移右边或者上面的最优解。 好久没做$DP$了。 ## 时间分层 ### [网络流24题]星际转移问题（half full） 想到了要建多个地球和月亮，但并不清楚怎么建分层图。 实际上就是枚举答案，然后每次跑个最大流，如果$maxflow=k$就可以了。 然后每一天分层，相当于是完全蒯一个新图过去（只蒯点），然后每个点要向下一天的点连容量为$+\infty$的边，因为人可以待着；对于每条这次走的航线$u\to v$，这一天的$u$向下一天的$v$连容量为$h_i$的边。 注意$S$向每天的地球，每天的月亮向$T$连容量为$k$的边。 ### $[HNOI2007]$紧急疏散（half half） 想了想直接建图貌似很不妙，而且直接对每个时间都蒯图空间复杂度会十分大，然后就凉了。 看了看网上的题解，大家怎么都这么强$\cdots\cdots$ 首先可以预处理出每个人到每个门的距离，这个简单$BFS$就好。 然后因为这题答案比较大，那么我们可以二分答案，然后每次重构图。 首先$S$向每个有人的点连一条容量为$1$的边，然后把每个门拆成$mid$个点，每个点朝在这个时候能到的门连一条容量为$1$的边，每个$x$时刻的门朝$x+1$连一个$inf$的边，朝$T$连一条容量为$1$的边，然后跑最大流验证。 实际上我感觉不用重构图，直接把所有的门建出来，然后只有当前$\le mid$时刻1的门才向$T$连边就可以了。然后撤销应该也比较方便。 ## 回路限制 利用度数限制建模。 一般情况下可以根据题目要求把四个方向拆开。 ### $[POI2010]Bridges$（zero half） 抱歉，我连二分答案都不会了。我觉得我其实是在借网络流复习基础。 首先看到最大值最小就二分答案，然后直接把$val\le mid$的边建出来，判有没有混合图欧拉回路。 ### $[bzoj4213]$贪吃蛇（zero full） 这题非常有意思，有很多套路值得学习。 首先我们发现题目的限制十分棘手，要考虑转化限制条件。 我们可以发现，如果蛇是一条环，那么它上面的每个点度数都为$2$；如果不是，那么它的开头和结尾度数都是$1$。 于是我们可以考虑利用度数这个限制，把度数转化为容量。~~尽管我知道但是还是没有想出来~~ 然而如果一个点直接向$S,T$连边，是难以判断它的答案是什么的。同时为了连边的方便，我们要让某些点输出$S$给予的流量，某些点接受流量给$T$。有一个非常重要的套路就是**黑白染色**。 我们将图黑白染色，然后让$S$向所有白色点连一条容量为$[2,2]$，费用为$0$的边，表示这个点如果要成环必须度数为$2$，让所有黑色点连一条同样的边向$T$ ；然后让所有白色点向相邻黑色点连一条容量为$[0,1]$，费用为$0$的边，表示可以让这些白色点与黑色点成蛇；同时我们让$S$向所有边界上的黑色点连一条容量为$[0,1]$，费用为$1$的边，让所有边界上的白色点向$T$连一条同样的边，表示可以通过给费用的方式帮你流一部分，来形成一条非成环的蛇。 然后就可以跑上下界最小费用可行流直接确定答案了。注意最终答案要$\div 2$，因为首尾各算了一次。 ### $[TJOI2013]$循环格（zero half） 做这题的时候我体验到了无论如何也想不出做法，明明有思路就是无法继续想下去的绝望。 然后看了题解发现自己想太多了。 **** 其实就是个很简单的题，首先一定是入度$=$出度$=1$，然后因为实际上出度和你这个点并没有什么关系，所以可以出度放左边，点放右边。 然后出度直接向四相邻连边，如果是非原本的方向费用就是$1$，然后就是二分图最小权匹配问题。这个就让所有边流量为$1$就可以直接跑费用流了。 另外注意这种问题长得像状压，因此做题需要注意。 ### $[TCSRM570\ 900]CurvyonRails$（full half） 我每次想的做法都是非常暴力而且奇怪的$\cdots\cdots$这也是老毛病了，发现不了性质，很烦。 实际上先套路黑白染色，然后$S\to$白连$\{2,0\}$的点，白向六个点连边——横、竖、四个弯。其中横竖的连$\{2,1\}$，其它的连$\{2,0\}$。然后每个这样的中转节点朝对应黑点连边，都是连$\{1,0\}$。最后黑点朝$T$连$\{2,0\}$。 直接跑最小费用最大流，验证是否满流即可。之前本来说要跑上下界费用流，但好像那样不能判是否可行。 我清楚地认识到这个做法不可能是正解做法，于是去看了题解。 $UPD:$这个做法假了，因为不能确定黑点是不是直的，如果要确定应该要再开一排节点，但这样也是错的，因为实际上每种情况只能有一个节点流流量，不知道怎么改。 **** 正解非常精妙。 首先我么可以看出，如果是一条直线，那么一定是连向同一行的两个点或者同一列的两个点。那么我们可以考虑进行拆点。 把每个点拆成分别代表连行和列的点，两白各被$S$连，两黑各连$T\{1,0\}$，意思就是如果各自流就没有问题。然后白各自向对应的黑（**只有两个点**）连$\{1,0\}$。然后再让行向列，列向行连$\{1,1\}$，表示如果这条边流了，那么意味着这个点连的两个点在一条直线上了，那么就必须要付出代价。 然后这样去跑$MCMF$，满流就表示有解，可以直接输出答案。 ### [清华集训2017]无限之环（half half） 想到了一半。明明这种题应该要能想出来的。 首先还是可以发现每个点满足条件就是入度=出度。然后为了方便，我们把每个点分成四个点表示四个方向。 然后就可以直接黑白染色相邻接口连边，无解就是流满不了或者黑白接口总数不一致。 然后考虑旋转，其实也很简单，就是分类讨论，考虑旋转到底是怎么变向的，因为直线型水管不能变向，也就意味着不会出现一次性变动两个方向。 然后就可以 （图来自$leoly$） 像这样建图就可以了。也就是分析一下每种水管旋转的具体影响。 这题带给我的想法就是，看起来越复杂的题就可以把模型建地越简单。 **** 另外我$yy$了一下，如果这题像我上题那种做法，每个节点拆成旋转的四种形态，然后也可以让白黑能连的形态连边，有几个接口流量就是几，如果这样能处理好黑方流量限制的问题的话，那么就能够做直线型水管能够转的问题了。救救孩子。 ## 闭合子图 一般情况是通过依赖关系建图，即选某个必须选另外某个。 实际上，不能去想如何建最大权闭合子图，而是去想转化后的最小割模型，用增广路表示一种方案的一部分，割代表花费的代价（某个条件不完成也是代价）。因为割一个条件就割掉了，要完成这个条件就要割掉所有的其它边，所以是正确的。 ### $[TJOI2015]$线性代数（half full） 想到选$a_i$必须选$-c_i$，然后一直在在纠结$a_i,a_j$怎么选$\cdots\cdots$然后凉了。 首先转化一下答案： $$ans=\sum_{i=1}^n((\sum_{j=1}^na_jb_{ji})-c_i)a_i$$ $$=\sum_{i=1}^n\sum_{j=1}^na_ia_jb_{ji}-\sum_{i=1}^nc_ia_i$$ 然后我们可以将$b_{ij}$当作一个点，权值为$b_{ij}$，然后向$i,j$连边，表示要产生$b_{ij}$的贡献必须有$a_i,a_j$。同时我们让$val_i=c_i$，表示选了$a_i$就要承受$-c_i$的贡献。 然后变成了最大权闭合子图裸题。 ### $[CF311E]Biologist$（full full） 感觉我的做法也是对的$\cdots\cdots$ 首先考虑最大权闭合子图怎么建。 把每个点拆成两个点，一个权值为$0$，一个权值为$v_i$，分别代表原性别和变性别。 每个条件向它指向的性别的权值对应的点连边，然后这个条件对应的点的权值就是$w_i$，如果这个点不选会有代价那么权值就是$w_i+g$。 然后求最大权闭合子图，再把答案减去$g\times$不选有代价的点的个数就是答案。 **** 网上的做法我认为应该是直接运用了最大权闭合子图的最小割模型，实质上是从最小割的角度研究的： 把每个性别为$0$的狗被$S$连，性别为$1$的狗连$T$，容量为$v_i$。 然后对于每个限制为$0$的条件，也与$S$连，容量为$w_i(+g)$。然后连向每条狗，容量为$+\infty$。这样就能保证一条增广路就是$S\to 0case\to 1dog\to T$，也就是说割意味着不满足，也就是要么不选这个条件，要么让狗变性。 限制为$1$的条件同理，与$T$连，容量类似。然后被每条狗连$+\infty$，这样增广路就是$S\to 0dog\to 1case\to T$，能够满足题目的依赖关系。 至于$S\to 0dog\to 0case,1dog\to 1case\to T$，显然都不会构成增广路。 然后直接用$\sum w_i-$最小割就可以了。注意从意义上理解不用$+g$。 感觉两种应该都可以吧？ ### $[CEOI2008]Order$（zero half） 我明白了，不能去想如何建最大权闭合子图，而是去想转化后的最小割模型，用增广路表示一种方案的一部分，割代表花费的代价（某个条件不完成也是代价）。因为割一个条件就割掉了，要完成这个条件就要割掉所有的其它边，所以是正确的。 **** 首先如果没有租机器的话就是最大权闭合子图。 如果有租机器，这个租的机器我们显然一个只能用一次。 所以我们把代表租机器的点拆开，对于每一个需要这个机器$y$的点$x$，我们在$x\to y$中间加一个点$u$，也就是$x\to u\to y$，然后让$x\to u,u\to y$的容量都设为租的价格，这样让$S\to x,y\to T$，那么一条增广路就形如$S\to x\to u\to y\to T$的形式，那么割$S\to x$代表不搞这个条件，$x\to u,u\to y$割任何一条边都代表租用，$y\to T$就代表买。这样就保证租用只能用一次。直接求最小割，把总收益减最小割就可以了。 实际上好像不用建这个点$u$，将$x\to y$的权值设成租用就可以了。 ### $[bzoj3774]$最优选择（zero half） 黑白染色套路好啊。 首先我们进行黑白染色，然后我们依然让白的被$S$连，黑的连$T$，容量就是控制它的代价。 然后我们让$S$向四相邻的点连边，容量为$+\infty$。显然这样就意味着，一个点被割掉，要么选它自己，要么让四相邻点都割掉。 然后还有不选这种操作。这样的话就让白的连$T$，黑的被$S$连，容量是它的收益。这样就保证割了这条边和它四相邻的点并不能通过四相邻占领的方式获得收益了。 $UPD$ ## 最小割转对偶图最短路 ### $[BJOI2010]$狼抓兔子（full half） 板子。 ### $[NOI2010]$海拔（full half） 有一些关于边方向的细节没有想清，需要注意。 首先观察可以发现在某些位置变成$1$就不用下来了，于是海拔非$0$即$1$，而且一定是分成两个连通块，否则一定可以变成这样使得答案更优。 于是那些$0-1$的边就可以看成割，于是就变成了求最小割。 于是这是平面图，就转化为了求最短路。 至于边的关系，我们建双向边，然后由于起点和终点，可以规定每条有向边的右边是$0$，左边是$1$，然后这样跑就可以满足要求了。 ## 距离限制 这类问题指的是，每一个点有多种选择，每种选择的编号递增。要求你选了一个点的编号之后，某些相关点的编号选择与它的距离有一定关系。 一般情况下是差不超过$d$。 我们把所有编号排成一列，然后让$S\to id_1\to id_2\to\cdots\to id_n\to T$，把选择的代价放在它的出边上（$S\to id_1$连$+\infty$边，这样问题转化为最小割。然后我们利用$+\infty$边对割进行限制。 譬如我选了一个点$x$，另外某个点只能选$[x-d,x+d]$，那么也就是说，我们要让那个点在割不在$[x-d,x+d]$的范围内的选择的时候让网络还有流，并且一定有流。 那么我们让这个点的$x$号选择连向下个点的$x-d$一个$+\infty$边，这样保证如果你割$x-d$之前的就还有流；让下个点的$x+d+1$连这个点的$x+1$一条$\infty$边，表示割$x+d$以后的也会有流。这样就可以直接求最小割了。 ### $[HNOI2013]$切糕（full half） 模型的直接应用。 ### $[CTSC2009]$移民站选址（zero half） 这么好的题居然这么老$\cdots\cdots$结论根本想不到。 ## $Hall$定理 有一道叫做$K-$完备匹配的题，它鸽了。 ### $[POI2009]Lyz$（half half） 想这道题的时候脑子不清醒，不过知道了线段树维护最大子段和这么一个操作。 首先显然是一个二分图。那么如果我们能满足要求，显然是完美匹配。 根据$Hall$定理，那么人的任意一个子集$S$都要与$\vert S\vert$个鞋子相邻。 显然肯定是连续的子区间的答案最劣，如果所有的连续子区间都满足，那么肯定就能够匹配，因为其它的集合肯定更能构造答案。 于是我们需要的条件是 $$\forall l\le r,\sum_{i=l}^rx_i\le(r+d-l+1)k$$ 设$v_i=x_i-k$，则 $$\forall l\le r,\sum_{i=l}^rv_i\le dk$$ 因此我们需要维护的就是一个最大子段和。 这个可以直接用线段树，维护区间和$Sum$，区间左端最优和$Lsz$，区间右端最优和$Rsz$，区间最大子段和$Siz$。 $pushup$的时候，$Sum$直接加，$Lsz$只有$Lsz[lson]/Sum[lson]+Lsz[rson]$两种可能，因为要么就维持左边最优解，要么就选择右边最优解，继续扩展的解不可能更优；$Rsz$亦然。$Siz$也很好维护，就是左右最优解$/Rsz[lson]+Lsz[rson]$中选一个。 至于人多于鞋子，直接判不合法就可以了。 ### $[CERC2016]Bipartite\ Blanket$（half half） 网上的博客题意模糊根本看不懂题$\cdots\cdots$ ## 费用递增 指的是物品选的越多费用越多。由于是最小费用最大流所以是可做的。 在费用递增模型中，通常要运用到拆点或连多条边的方法来表示每次增加的费用。 理论上来说这种模型的每个物品的费用应该是独立的，这样建模很方便。 似乎有人把这种类型的题称为凸函数费用题型。但我觉得它有时候并不凸。 ### $[NOI2012]$美食节（zero half） 连费用递增的模型都想错了$\cdots\cdots$ 首先每个同学的等待时间是不大好算的，要转化成某道做出来的菜对总答案的贡献。 考虑一个厨师一共做了$x$道菜，那么第$i$道菜的贡献就是$time_i\times (x-i+1)$，显然不太方便，因此我们可以倒过来，倒数第$i$道菜的贡献就是$time_i\times i$了。 因此可以这么建图：$S\to$第$i$个蔬菜连$\{p_i,0\}$，把每个厨师拆成蔬菜个数个点，每个蔬菜朝每个拆掉的点连$\{1,time_{ij}\times k\}$，然后每个厨师的各个点$\to T$连$\{1,0\}$。这样就可以跑最小费用最大流了。然而它的时间复杂度是$O(spfa\times n\sum_p^2)$（当然用$dinic$会快上不少，在哪带根号我也不知道），即使假设$O(spfa)=O(m)$也并不能通过。 因此我们考虑优化建图，实际上可以发现每个厨师要是做倒数第$i$道菜的点没有被增广那么第$i+1$道菜的点显然也不能被增广。 那么我们可以找到一条增广路后再把这个厨师的下一个点加进来，这样复杂度变成了$O(spfa\times n\sum_p+\sum_p^2)$，就可以过了。 $dinic$怎么做啊$\cdots\cdots$ 而且感觉拆点好像没意义啊直接加在原来那个点不好吗$\cdots\cdots$ ### $[JSOI2009]$球队收益/球队预算（half half） 大概还是想出了要限制一场比赛的流量。应该是题目做少了。 **** 首先考虑如果$D_i=0$怎么做。 这样的情况下输了没有影响，那么显然就是费用递增模型，具体来说我们让$S\to$比赛连$\{1,0\}$边，然后比赛朝两个队伍连$\{1,0\}$边，每支队伍向$T$连$\{1,cost\}$的多条边，$cost$代表每胜利一次不断增加的费用。然后直接跑费用流就可以了。 对于有$D_i$的情况，直接做并不是费用递增模型，很难处理费用。即使能连，边数也非常大。 因此我们可以假设两支球队都输了，那么现在每支球队赢一场不仅可以多赢一场，还可以少输一场，这样就消去了对另一只球队的影响。 然后假设当前赢$a$输$b$，那么多赢一场的增收是$C_i(2a+1)-D_i(2b-1)$，又因为$C_i>D_i$，那么赢地越多费用越大，转化为费用递增模型。只要把上面那个 $cost$改成这样的形式就可以了。 我一直在纠结比赛之间的关系怎么办，但实际上转化完之后就是独立的了，可以直接按胜利的方式建边。 ### $[WC2007]$剪刀石头布（zero half） 这题很有意思，我毫无想法。 首先考虑三元环如果合法，那么每个点在这个环中都有一个入度和一个出度。 然后你发现这并没有什么用。因为那样要考虑三个点的贡献。 然后你可以考虑不合法。那么总有一个点入/出度为$2$。 我们考虑枚举这个出度为$2$的点。因为是完全图，对于所有出度为$d$的点来说，它能产生的贡献就是$-\binom{d}{2}=-\frac{d(d-1)}{2}=-\frac{d^2}{2}+\frac{d}{2}$。 注意我们求的是$\sum$，于是$\sum\frac{d}{2}=\frac{d(d-1)}{4}$（为了避免一些不必要的麻烦，我们可以最后与其它要除$2$的一起除那个$2$）。剩下的$\frac{d}{2}$满足费用递增模型，因为入度在我们的枚举中不产生贡献，那么套路就跟上面那道题一样，给每条边开一个点，然后让这个点连向两个顶点，然后再连费用递增边。 其实好像网上也有不化简的做法，本质上类似。 另外$d=1$无所谓，两项都是$0$。 ## 签到问题 签到问题的模型非常妙，以至于我一开始并没有看懂这个模型是在干什么。 这类问题通常会限制让你必须遍历一些点，或者一些点必须遍历对应的次数。 把每个点拆成两个点，一个点连$T$，一个点被$S$连。 连$T$的点称为**签到点**，设为$E_i$；被$S$连的点称为**出发点**，设为$P_i$。$\sout{Prologue,Epilogue}$ 那么，从许多点流到签到点的过程就被称为**“签到”**。 这里的描述比较谜，来看下面的题目吧。 ### [网络流24题]餐巾计划（zero half） 因为不知道签到问题是什么意思，只好看了题解。 在这个题目中，“签到”指的是每天需要提供餐巾，以每天为一个点，餐巾数量为签到次数。 那么，把每天拆成两个点，一个点连$T\{x_i,0\}$，一个点被$S$连$\{x_i,0\}$，分别表示当前这一天需要$x_i$个点签到，同时签完到之后还有$x_i$个点可以留给以后用。 那么我们就可以非常简单地建立三种情况： 直接买，$S\to E_i\{+\infty,p\}$； 快洗，$P_i\to E_{i+m}\{+\infty,f\}$； 慢洗，$P_i\to E_{i+n}\{+\infty,s\}$。 **注意，当前的餐巾可以放在之后再洗留给更后面的点签到**，因此$P_i\to P_{i+1}\{+\infty,0\}$。 然后直接最小费用最大流。 ### $[SDOI2010]$星际竞速（full half） 模型的直接应用。 注意瞬移就是$S\to E_i\{1,a_i\}$，然后移动就是中间的连接过程。 题目给出的条件其实就是告诉你是$DAG$，如果原图不是$DAG$，似乎是做不了的。 ### $[ZJOI2011]$营救皮卡丘（half half） 这题充分地暴露了我的**实现细节能力不足**，我觉得需要之后再去找网络流题进行训练。 首先我猜到了一个结论，就是当前点集内走一定会走最短路。~~虽然它很显然~~ 然后我想到了除了$0$号出发点是$S\to P_0\{k,0\}$之外，其它点都只需要一个人访问就可以了。然后就觉得不能建$O(n^2)$条边，而且也不能清楚当前走到了哪些点就不能直接连，然后就凉了。 首先这样做肯定是对的，而且其它边的流量只要是$1$就可以了，因为签到只用签一次。 然后正确性也是对的，因为你要跑最大流，也就意味着每条边要流满，那么肯定所有的$E_0\to T$都会被光顾，那么就没问题。 注意每个点朝编号比它大的所有的点连边，费用为**当前状态下**的最短路。最短路用$Floyd$处理就可以了。 ## 区间型线性规划 这类问题通常是一种特殊的线性规划问题，它们具有区间的性质，即每个变量会出现在一段连续区间内的不等式里。 有一个解决这类问题的套路： 首先添加辅助变量，让不等式变为等式，这个怎么方便怎么来； 然后将等式差分（添加$eq_0,eq_{n+1}$，都是$0=0$），如果这道题的变量都有区间性质的话，那么最后就会出现每个变量一正一负处在两个等式里的情况。 最后将每个等式建点，常数按正负与$S/T$连边，相等关系视为流量平衡，变量视为流量转移，也就是我们按照变量的变化进行连边，流量设为变量变化上下界，费用就是变量$+1$需要的代价。 同样，看看下面的例子。 ### $[NOI2008]$志愿者招募（zero half） 连线性规划都快忘了，还问了下旁边在文化课上学过这节课的同学。 首先设第$i$**类**的志愿者数量是$x_i$，这个题目的要求也就是对于第$j$天使得$\sum x_i[i\in j]\ge a_j$。 添加辅助变量，即$\sum x_i[i\in j]-y_j= a_j(y_j\ge 0)$ 然后将等式差分（注意$0,n+1$号等式也要加进来），这样每个$x_i$只会在两个等式里出现，我们分别设它们为$s_i,t_i$。 那么，因为我们把常数$diff_i\ge 0$的被$S$连了，我们设入表示负，出表示正（（当然常数项是反过来的，等式左边的负就是等式右边的正），从$s_i$向$t_i$连$\{+\infty,c_i\}$**（无论$s_i,t_i$连的是$S$还是$T$）**。 常数项就与源汇连$\{diff_i,0\}$，求最小费用最大流就可以了。 ### $[NEERC2016]Delight\ for\ a\ Cat$（half half） 我觉得一个式子带有两个不等式不太好处理，然后就凉了。 **** 首先虽然它是一个区间询问，但是显然你可以把一段区间的总和累到一个不等式里。 譬如我们设$x_i=1$表示做第一个，$=0$表示做第二个。 那么对于某个连续的区间，它需要满足$k-t_2\ge\sum_{i=1}^kx_i\ge t_1$。 我们添加辅助变量，也就是$k-t_2-z=\sum_{i=1}^kx_i=t_1+y$，这么写是因为有两个不等式方便看。 然后我们把这个等式拆成两个等式，就像这样 $$\sum_{i=1}^kx_i=t_1+y$$ $$\sum_{i=1}^kx_i=k-t_2-z$$ 然后把所有的等式都这么列，之后再差分（为了方便这里直接前后添加两个$0=0$） $$\sum_{i=1}^kx_i=t_1+y$$ $$0=k-t_2-z-t_1-y$$ $$-\sum_{i=1}^kx_i=-k+t_2+z$$ 整理一下 $$\sum_{i=1}^kx_i-y=t_1$$ $$y+z=k-t_2-t_1$$ $$-\sum_{i=1}^kx_i-z=-k+t_2$$ 我们惊讶地发现居然每个变量都出现了两次，一次正，一次负。 那么可以跟上题一样的套路建图跑最大费用最大流了。 你可能会考虑到某个点可能只有流入/出没有流出/入的情况。但这种情况是**无解**的（因为这意味着等式左右正负都不相同了），所以不用担心。 另外因为我们只考虑做第一个事情，那么求两个费用不太方便，我们可以用一个老套路，就是先假设全部做第二个事情，做第一个事情的收益就是第一个减第二个。 ## 模拟费用流 这类问题一般情况下是指能够直观地看出一个费用流解法，但是该解法效率太低需要使用其它算法模拟费用流进行过程的问题。 对于这类题型，虽然先想费用流做法很很有必要，但首先得找一个切入点再进行建模。如果从建模角度不好下手也可以考虑考虑其它解法。如果已经想到了费用流做法，那么就要考虑这个费用流的执行过程实质是在干什么，它有什么样的性质可以优化，通过这样的方式去解题。 ~~听说$\sout{WC}$会讲，赶紧学一学。~~ ### $[CF280D]k-Maximum\ Subsequence\ Sum$（zero half） 我连费用流解法都没想出来，连区间建模都不会了，我是傻逼。 首先有一个比较显然的费用流做法，就是把区间连成一条链，注意要把点权转化为边权所以要拆成$n+1$个点，然后每个点都与$S,T$连$\{1,0\}$边。每条边的流量都是$1$。 然后限制流量为$k$跑一次$dinic$最大费用流就可以求出答案，注意是不超过$k$个所以如果增广费用为负数也要退出。 但这样的理论效率是$O(nmk)/O(n\sqrt mk)?$的，不能通过此题~~说不定$\sout{dinic}$能卡过去~~。 我们考虑费用流的增广实际上是在进行一种贪心，这种贪心每次有两种选择，选择一个区间，或者从原来选择的区间里删除连续一段（并选择另一段相邻的连续区间）。 那么我们实际上要维护的就是：区间最大子段和与区间取反（改变正负）这两个东西。它可以用线段树维护，然后每次询问就查询并修改$k$次，最后把修改复原。 但是这个东西具体怎么维护呢？因为有区间取反，所以我们需要维护的是$\cdots\cdots$ **区间和、最大子段和、最小子段和、前缀最大和、后缀最大和、前缀最小和、后缀最小和、取反标记**。 究极快乐$\rm .jpg$ ### $[NEERC2016]Mole\ Tunnels$（half half） 我觉得我大概是不会模拟费用流了$\cdots\cdots$就是想不清楚。 首先$O(n^2)$条边的暴力费用流很显然，然而我只会这个东西$qwq$ 然后保留树结构，每个点连源汇的做法更加优秀，只有$O(n)$条边，我连这个都没想出来。注意树上的边流量设为$+\infty$。每次改对应点朝$S$那一边的流量（$0\to 1$），在残量网络上增广就可以了。 再考虑这个费用流的实质是什么。也是在这棵树上选择一段路径，或者删掉若干段路径（并选择一段路径）。由于树高是$O(\log)$的，那么所有的修改也是$O(\log)$的。 实际上，我们可以暴力维护子树内有果子最短路及其位置，然后模拟费用流的增广过程。我们对于一个点找到它的最近点（不断跳父亲），然后让反向边流量$+1$（正向边流量显然为正无穷），因此在这个过程中要更新这一段路径的答案，还要更新更上面祖先的答案。 因为只有两个子树，树高也为$O(\log n)$，所以并没有什么问题。 ### $[NOI2017]$蔬菜（zero half） 光顾着想费用流如何建模，忘了最基本的推题目性质，好好刷刷$ARC$练练吧，这明明是道不难的贪心题，而且我去年打$CFDiv.3$的时候就想到了这个套路，实在不应该。 首先一个重要的结论就是**倒着贪心**，这个结论并不难想，因为从前面贪心会有过期的限制，但如果从后面贪心，前面肯定不会过期，而且越赚的菜肯定是越早卖完越优秀。 然后我们还要把$s_i$分开，就是**把一种蔬菜多拆$1$份，那一份大小为$1$，可以获得的收益是$a_i+s_i$。** 如果我们要写暴力的的话，就再把前面那些蔬菜拆成$day_i$份，每一份量相同（除最后一份是剩下的），然后我们可以直接用优先队列维护这个贪心，每次将对应的蔬菜加入大根堆，然后取出前$m$个就可以了。如果对于每个询问都回答的话，好像是$O(n^2mq\log n)$。~~居然可以获得$\sout{60pts}$~~ 让我们考虑正解怎么做。因为我不会并查集所以参考的是$\rm shadowice1984$的做法。~~我感觉他写得太好了所以就不写了，如果我哪天要码这道题了，我就会来补充一下实现细节。他的做法就在洛谷题解里。~~ 注意一些细节比如我们找菜的完全变质时间用的是上取整，以及如果最后还没变质的菜要放到$p$的位置。 # $Summary$ **转化为二分图**是一个非常常见的套路。其有多种方式，譬如黑白染色、行列建点、利用某个性质拆分点集等。很多题都有出现。 有一种能强行让两个点流量相等的方法，见$[WF2011]$那道题。虽然有很多限制，但非常好用。 对于某个难以转化为点的情况，可考虑其是否能通过其它情况转化而来，如果可以，那么转过来的情况（若有代价就可以当成费用）就可以当作一条边去组合其它的情况。譬如$[TCSRM570\ 900]$。 图论上的网络流，点少边多考虑直接建$O(n^2)$条边，费用就是最短路长度之类的可以用$Floyd$；点多就直接保留原图结构（这种题有可能是模拟费用流）。 考虑细节的能力不够，这个不仅要靠代码还得考刷题的时候想清楚。 容易想假想多想少，老毛病又犯了。