老鼠进洞问题
Basori_Tiara · · 个人记录
应该写进模拟费用流里面的，但是问题太多了就拿出来了。
实际上老鼠进洞问题看下来很多转化成反悔贪心是更方便理解的，别的模拟费用流感觉是直接跑更方便理解。
先看第一个问题：
现在在数轴上有若干个老鼠和若干个洞，分配老鼠进洞使得老鼠移动总距离最小。
我们考虑建立这样一个费用流模型：
因为那个傻逼鼠标太不好发挥了，所以蓝边只画了一条，实际上相邻的都应该加一条。
考虑这样直接费用流就是对的，但是我们没法费用流，所以我们模拟费用流。
考虑费用流可以怎么跑？
首先辖集把跑，然后消圈。
那我们把两个相邻的画出来
你发现如果中间那个老鼠进了左边的洞，左边的边一反出绿色的边，就出现了蓝色的环，而这个蓝色的环除了中间的边居然别的边都没有权值！！！！
而这个值列个式子把只和老鼠及其匹配洞的价值单独拿出来最优化，对于每个洞我们就能拿一大堆负环然后拿过来更新。
同样的，一个老鼠也能达到相同的效果，拆拆式子就行了。
这个就是最初的老鼠进洞问题。
然后是第二个问题：
还是老鼠进洞，但是一个洞可以容纳若干个老鼠，具体的是一个输入的数。
有一个基础的思路就是把洞的影分身全拿出来建点，但是很明显这个是平方级别的，不够帅气和优秀！
考虑一个洞真的需要那么多个吗？完全不需要啊，我们根本没必要对于一个洞，把所有洞全开出来啊，我们开一个结构体，里面存放两种元素，一个是这个洞的数量，一个是这个洞的贡献。
然后考虑对于每个老鼠，他最多
这两个东西本质上是相同的，因为上面的流量没变我们就懒得管，而下面的流量是可以通过维护上面所说的结构体直接维护的。
具体时间复杂度证明大概是这样的：
考虑一个洞，他牛了一大片，那么这一大段的贡献就被统一地拿下了，然后剩下的流量才流得下去才能被当成人看，也就是说，每当我们操作一个洞地时候，无论前面有多少流量，最后最多剩下来两个老鼠，其中一个是我们增广/找负环地时候满流了剩地，另一个是我们把所有老鼠的交换贡献集成到了这个洞上面——可以这么做的原因是增广路的形状非常奇怪，后面找负环都只会找到这个洞，而计算交接贡献也是，当然这些我们都不关心，很容易发现，我们最后操作了
然后是第三个问题：
#455. 【UER #8】雪灾与外卖
考虑现在每个点不仅有容量还有价值，转化到原费用流问题上就是下面边多了边权，直接加上去即可。
然后是第四个问题：P3837
这个问题相当于是有些老鼠有些洞，洞无限大，老鼠可以触发隐藏按钮然后吓我一跳我释放影分身十字斩，要求每个老鼠至少一个分身进洞，每个洞内至少一个分身。
但是我还没写，所以后面再更。
刚才把他写完了，我们考虑这个问题可以转化为：
首先各插入一个，要求这一个必须被操作一下。
然后给个inf。
然后仿照雪灾与外卖就做完了zzz
我们来看第五个问题：P6943，树上老鼠进洞，听说场上没人切。
好的，经过一个晚上的思考，现在会了。
首先点权和是1e6级别的，我们可以用一个原始做法，就是把老鼠和洞全拆了，当然也可以不这么做，仿照例2。
这个有一个优美性质就是路径和路径相交是不优的。
然后我们考虑怎么模拟费用流，考虑源点连正汇点连负，那么费用流的流法就是流上LCA然后再流下来。
我们把两个点的点权拿出来（最开始时都是dep，即到根链的长度），然后考虑最开始的移动距离就是
但是后面还有可能退流或者说反悔。
这张图中，原本下面的+-都配对，然后回到上面，发现上面的+和下面的-配对会更优，那么这个时候容易发现图中橙色部分出现了负环。
橙色部分的负环实际上是两个部分，一部分是在配对的时候就发现的，也就是图中下面那部分，实际上这个部分是
而用反悔贪心也很好理解，原本式子是
还有一个很难理解的地方，就是如果两边同时交叉选了怎么办？
很明显不可能交叉选，因为交叉选一定不优，这两对正负号中间的路径被多走了两次。
就像这样，紫色的匹配必然比蓝色的匹配不劣，所以我们不可能取到紫色匹配，所以这样一定是正确的。
具体操作的时候把权值取出来后把
因为洞必须装满所以洞需要给个-inf的权。
当然这一切的基础都在
是个很厉害的题，困扰了我几乎是半天（虽然有好几个小时都在看zhihu）
第六个问题：P4217，取个名就叫坡上老鼠进洞吧。
如果你成功地将模型转化了就会发现，这次洞是有代价有容量的，而中间的连边左到右和右到左是完全不一样的，理解为上坡/下坡。
像这样的题，一般是只能数据结构暴力维护模拟费用流了。
先来讲一下模型：
大概是长这个样子，红边是黑边的反向边，画出来等下要用到费用应是
因为我们的枚举增广顺序是从左到右，所以蓝边的反向边压根派不上用场啊。
那就让我们来看一下假设现在枚举到了点i这个会有什么反应，在这张图上面一个点有两种方式可走：往右走和往左走。
现在流了一下绿边，考虑从左往右的贡献是单一的，首先拿到他的价值
流了绿边之后会鼓动风雨从右边到左边的红边的流量变化，比如这里假设流进去了
他就会走橙色的边，看到了吗，因为
也就是说，在操作左增广路的时候，不是单纯的
而哪些
而当我们左修改操作的时候，我们应该找到这些地方的流量的
时间复杂度证明：
左到右的增广时间复杂度显然，每次操作必然灌满一整个源点到
上面这些东西都是可以线段树维护的，时间复杂度
看上去是比较难写的题，也没有有趣的费用流性质。