一些网络流经典建模

· · 个人记录

在模拟赛被几道网络流板子爆杀了。自闭了，加训网络流。

文理分科模型

这个东西大概是说，每个人有两个选择，然后给出一些集合，这个集合里的人全部满足某个选择，则可以获得一些收益，否则还可能有惩罚。

二者选其一的模型，可以想到最小割。我们不妨设两个选择为 0,1，则建立源点 S 表示 0，汇点 T 表示 1。即如果在最终的割中，某个点与源点是同一集合则选 0，否则选 1。然后对于一个集合，不妨设它要求全选 0，则我们建立虚点向源点连边权为失败代价加收益流量的边，向集合内所有点连流量为 \infty 的边。注意到，这样限制了我们要么将集合内的所有点与汇点不连通（即选 0），要么割掉虚点向源点连的边。我们假设一开始所有的任务都能完成，减去最小割即可。

CF311E，P4313，P1646。

有 n 个 01 数 v_i，已经决定了 m 个，有 k 个二元组 (x,y)，满足要把 v_x\operatorname{xor}v_y 加和入答案，决定剩下 n-m 个数，最小化答案。

还是二者选其一，但这里没有明显的集合模型。我们不妨先研究一下对于两个确定的数，我们如何表示代价。事实上，我们可以让 v_i=1 的向源点连边，v_i=0 的向汇点连边，流量均为 \infty。然后对于每对限制，我们在 x,y 之间连流量为 1 的边。这样，对于已经确定的，我们就不得不割这条 1 的边以保证不连通。接着，我们发现，如果存在一个未确定的点 u 满足 (x,u),(y,u) 均存在，且 v_x,v_y 已确定为不同的数。则 (x,u),(y,u) 必须割去一条，原因显然。容易发现，我们的模型和刚刚是类似的，只不过这里不确定的边，我们不再显式做出决定，而是如果不得不做出决定，根据割掉哪条边做出决定。

更进一步地，我们还能求出如何最小化选的 1 个数。考虑将上述连边中的 1 替换为一个足够大的数 x。然后汇点向每个未确定的点连流量为 1 的边。此时，如果我们对于一个点选择了 1，则我们还得割掉这条边。而由于 x 足够大，我们会在最小化答案的基础上来做这件事情。

流量平衡模型

这个东西意思是，我们需要在保证平衡的情况下，进行一些转移。比如这里 +1 那里也要 +1，这里 +1 那里就要 -1 等。此时我们发现，网络流的流量平衡性质可以很好完成这个限制。

一般来说，我们会有一些东西需要填满，有一些东西需要补充。或者说，需要同时进行操作的地方满足二分的性质。此时我们就能建出一张二分图，将同时操作的两个点之间连边。这样，我们进行其中一个操作的时候，就势必要把操作的这个流量也流到另一个地方去。

P3511，CF277E，P5038，有 m 种操作，把 序列上 [l_i,r_i] 之间的点全部 +1 或 -1，用最少次操作把序列全部变为相同。

最大权闭合子图

这个就是说，你选 \rm A，就必须先选 \rm B。显然，如果不存在负权值的东西，我们直接全选就完事了。而考虑负权，很自然地，我们把点分成了两个集合。我们让源汇点分别朝其对应集合内的点连流量为权值绝对值的边。然后对于每一种限制，在它们两个之间连边权为 \infty 的边。先假设正的全选，然后减去最小割即可。注意到，一旦选了一个正的（即不割），所有它对应的负的都需要被割掉。集合内的边不造成影响，意义显然。

P4174，P2805。

修车模型

这个问题是，我们修车是同时进行的，在修一个人的车的时候，另一个人也在等待，也要计入时间。所以我们考虑将每个工人拆成 n 个点，表示它修倒数第 i 辆车的代价。这样我们把车和人拆成二分图，连边的边权就是 i\times w，表示有 i 个人要等 w 的时间。

P2053，P2050。

割字典序最小模型

不知道算不算一个模型，因为我就见过一道题。

考虑字典序最小，我们先看看 1 有没有可能成为割集的一部分，具体来讲，我们看看在任意的一个最小割中，1 两边的点在不在同一集合内。如果在，1 就在最小割内，删去这条边，对 2 重复做上述过程即可。注意，这个仅对 \rm DAG 成立，出现环可能会误判割边。

P3308。

切糕模型

大概是说需要满足 i 选的东西和 j 选的东西 \ge k。考虑设能选的东西的值域为 n，则我们对于每个点建立一个长为 n+1 的链，且 (i,i+1) 边的流量为 w_i，如果我们割这条边，表示选 w_i。然后我们让源点连所有 1 号点，所有 n+1 号点连汇点。这样如果没有限制，显然我们会割掉最小的那些边。接着，对于 i,j，我们连 i_o,j_{o+k}，流量为 \infty 的边。发现，如果我们选择了 i_{o-1}，而 j 处选择了 j_{o+k} 之前的点，就会导致源汇仍然连通。\le 的情况是类似的，边换一下方向即可。

P3227，P6054。

先写这么多吧，再遇见再写。

记得回头写一下上下界网络流和可行流。