就是你先海草一下,然后 The 2nd Universal Cup. Stage 5: Northern, L.LCSLCSLCS 这个题给出了怎么
ur 25 C. 装配序列 2log
理性理解 uer8 雪灾与外卖
之前写了一个 感性理解 uer8 雪灾与外卖,但是太感性了,所以再写个理性的!!!
先假设你会费用流建图了。从左往右加点维护最小费用最大流。在左边加上无穷个
我们提到流量时,指的总是链上的边。
先考虑
Observation 1
如果一条边流量为
Corollary 1
如果一条边在两个不同时刻流量为
我们让一个点和它左边的边编号相同。
考虑找到最右的流量变为
于是根据上面的结论,这次增广的效果就是把边
Observation 2
由于
最右的流量变为
Theorem
我们可能做的事情只有以下几种:
加入一个餐馆,不做操作/走一个不经过反悔边的负环。
加入一个送餐员,匹配一个未匹配的餐馆。
加入一个餐馆,撤销进行了操作4且未被撤销的送餐员中最后加入的那个的操作,并匹配这个送餐员。
加入一个送餐员,撤销进行了操作3且未被撤销的餐馆中最后加入的那个的操作,并匹配这个餐馆。
Proof
对时间归纳。先考虑加入送餐员
如果有边
Observation 3
如果一个之前的餐馆进行了操作3且未被撤销,那么它左侧那条边流量一定是向右的。
Proof
显然刚进行完这个操作时它是向右的。操作2不会改变这条边,操作1/3不会让这条边向右的流量减小。操作4会撤销最后的操作3,不可能让这条边的流量减到
所以餐馆
另一方面,加入餐馆
所以所有经过边
然后考虑加入餐馆
Observation 3'
如果一个之前的送餐员进行了操作4且未被撤销,那么它左侧那条边流量一定是向左的。
Proof
显然刚进行完这个操作时它是向左的。操作1不会改变这条边(因为限制了没走反悔边),操作2/4不会让这条边向左的流量减小。操作3会撤销最后的操作4,不可能让这条边的流量减到
所以送餐员
另一方面,加入送餐员
所以所有经过边
我们要维护这四种操作。使用两个堆分别维护加入餐馆时可能的负环和加入送餐员时可能的增广路的情况。
加入一个送餐员。我们在增广路堆中找到堆顶
,给答案加上 ,并往负环堆中加入 (提供操作3的机会)。加入一个餐馆。我们在负环堆中找到堆顶
,如果 则没有负环,往增广路堆中加入 (提供操作2的机会);否则给答案加上 ,并往增广路堆中加入 (提供操作4的机会),往负环堆中加入 (提供操作1的机会)。
但是这里我们把可能不是最后加入的也扔进堆里了,这还对吗?注意到不是最后一个的话,这么算出来的代价只会更大,因为它之后的操作又生成了若干反悔边(它们可能被撤销,但是刚加入它时就有的那些不可能被撤销),而反悔这些边减少的代价并没有被更新。而最后一个本来就是代价最小的,现在肯定还是代价最小的,所以没有问题。
至于