参考：
https://blog.csdn.net/litble/article/details/88410435
https://www.mina.moe/archives/11762
一堆草稿...
令 ????为某种方式得到一个洞的权值，????为某种方式得到一只兔子的权值，????为兔子的坐标，????为洞的坐标，????为一个洞的附加权值。
一只兔子b如果选择洞a，总权值的增加量即为$w_a-y_a+x_b$。之后一个好洞c替换这个坏洞时，总权值又会增加$-(w_a-y_a)+y_c-2x_b$，对于好洞c来说，它找到了一只兔子，并且产生了$-(w_a-y_a)+y_c-2x_b$的贡献，因此我们可以新增加一只权值为$-(w_a-y_a)-x_b$的兔子。
一个洞 ??如果找到了兔子 ??，总权值的增加量 ????+????+????。之后一个兔子 ??抢走了这个洞时，总权值又会增加 ????−????−2????，对于 ??来说，它找到了一个洞，而 ??也不会因此无家可归，因为当我们处理 ??的时候，我们肯定为它分配了在它前面的洞，后来 ??找到了 ??，现在 ??把 ??赶走了，??显然可以回去找之前分配给它的洞，赶走里面住的兔子，以此类推。这样，一切又回到了 ??没有发现 ??时的模样，因此，对于 ??来说，我们可以新增一个权值为 −????−2????的洞。
一个洞 ??如果找到了兔子 ??，总权值增加量 ????+????+????。之后一个新的洞 ??替代了 ??，总权值又会增加 ????+????−????−????，对于 ??来说，它找到了一个权值为 −????−????的兔子，因此我们新增一个这样的兔子。
令$x_i$为兔子的坐标，$y_i$为洞的坐标，$s_i$为一个洞的附加权值。
一只兔子b如果选择洞a，总权值的增加量即为$s_a-y_a+x_b$。之后一个好洞c替换这个坏洞a时，总权值又会增加$-(s_a-y_a+x_b)+y_c+s_c-x_b=-s_a+y_a+y_c+s_c-2x_b$，对于好洞c来说，它找到了一只兔子，并且产生了$-s_a+y_a+y_c+s_c-2x_b$的贡献，因此我们可以新增加一只权值为$(-s_a+y_a+y_c+s_c-2x_b)-($的兔子。
一个洞 ??如果找到了兔子 ??，总权值的增加量 ????+????+????。之后一个兔子 ??抢走了这个洞时，总权值又会增加 ????−????−2????，对于 ??来说，它找到了一个洞，而 ??也不会因此无家可归，因为当我们处理 ??的时候，我们肯定为它分配了在它前面的洞，后来 ??找到了 ??，现在 ??把 ??赶走了，??显然可以回去找之前分配给它的洞，赶走里面住的兔子，以此类推。这样，一切又回到了 ??没有发现 ??时的模样，因此，对于 ??来说，我们可以新增一个权值为 −????−2????的洞。
一个洞 ??如果找到了兔子 ??，总权值增加量 ????+????+????。之后一个新的洞 ??替代了 ??，总权值又会增加 ????+????−????−????，对于 ??来说，它找到了一个权值为 −????−????的兔子，因此我们新增一个这样的兔子。
将兔子和洞从左到右排序，依次考虑。
匹配有两种：兔子与其之前的洞匹配(a类)，洞与其之前的兔子匹配(b类)。
具体来说：
加入一个兔子，先与已经被考虑过的洞中剩余未被匹配的洞中最靠后的匹配（如果没有，就假设左侧无限远处有无限个的洞），可能要与之前的某个兔子交换洞。
遇到一个洞，可能会将之前某只兔子改为与其匹配。
设兔子的坐标为$x_i$，洞的坐标为$y_i$，洞的附加权值为$s_i$。
维护一个堆q1，存放"已经被考虑过的洞中剩余未被匹配的洞"的信息。
维护一个堆q2，存放"可能会在加入新洞的时候改变匹配的兔子"的信息。
一个兔子b选择洞a，总权值增加$s_a-y_a+x_b$。之后一个好洞c替换a时，总权值增加$-(s_a-y_a+x_b)+(y_c+s_c-x_b)=y_c+s_c-s_a+y_a-2x_b$。因此q2中放入一个$-s_a+y_a-2x_b$
我完全没看出来以下算法跟费用流有什么关系，也没看出来为什么是对的...
一个简化版的问题：如果每个洞容量都为1?
将兔子和洞从左到右排序，依次考虑。
匹配有两种：兔子与其之前的洞匹配(a类)，洞与其之前的兔子匹配(b类)。
几种情况：
(废弃,可以发现无论如何都不可能更优)1.a类兔子A与之前的洞B匹配，可能洞会被A之后的兔子C抢走(指A与C交换它们所在的洞)("抢"前后都是a类)
1.a类兔子A与之前的洞B匹配，可能兔子会被A之后的洞C抢走,B就返回未被匹配时的状态("抢"前后由a类变成b类)
2.b类兔子A与之后的洞B匹配，可能洞会被B之后的兔子抢走，同时A回到前一次分配给它的洞(可能还会"递归"地将一些其他兔子赶回它们前一次所在的洞)("抢"前后由b类变成a类)
3.每遇到一个洞，都优先从
具体来说：
设兔子i的坐标为$x_i$，洞i的坐标为$y_i$，洞i的附加权值为$s_i$。
维护两个堆q1,q2，分别存放之前未使用的兔子/洞的"权值"。（刚插入堆的洞i的权值为$s_i-y_i$，兔子i的权值为$$）
遇到一个兔子b，先在q2中取出一个权值最小的洞(权值为a)，与之匹配，产生贡献为$x_b+a$。如果有一个兔子d，原来匹配的洞权值是c(c,d间的匹配是a类)，那么可能要改为d匹配洞a，b匹配洞c。可以发现修改前后贡献不变（都为$x_b+a+x_d+c$），因此在q2中放入一个权值为$$
问题：
数轴上有一些兔子和洞。一个兔子必须进一个洞，一个洞可以进一定容量的兔子(每个洞容量可能不同)。兔子可以向两边走，洞每进一个兔子需要一定额外费用(每个洞可能不同)，最小化兔子行走的距离及选择的洞的额外费用之和。
我完全没看出来以下算法跟费用流有什么关系，也没看出来为什么是对的...
#猜了一下，大概是这样的意思：由于这个可以表示为费用流模型，且最大流是已知的（就是兔子数），如果任意得到一个方案，只需要不断做能使费用和变小的调整操作，最终一定能得到一种最优方案（这个结论真的对吗，我不会证）?
一个简化版的问题：如果每个洞容量都为1?
将兔子和洞从左到右排序，依次考虑。
设兔子i的坐标为$x_i$，洞i的坐标为$y_i$，洞i的附加权值为$s_i$。
维护两个堆q1,q2，分别存放之前未使用的兔子/洞的代价。（代价是人为定义的，新插入堆的洞i的权值为$s_i-y_i$，兔子i的权值为$$）
#匹配有两种：兔子与其之前的洞匹配(a类)，洞与其之前的兔子匹配(b类)。
遇到一个兔子A，先把它与q2中代价最小(设代价为v)的洞匹配（如果没有了就假设左侧无限远处有无限个洞，这是由于所有兔子都必须匹配）。产生贡献$x_A+v$
可能有之后的兔子抢夺这个洞，。
可能有之后的洞(设为C)抢夺这个兔子，抢夺之后贡献变为$y_C-x_A+s_C$，增加了$y_C+s_C-2x_A-v$，因此向q1中放入一个权值为$-2x_A-v$的兔子来模拟撤销
遇到一个洞B，先把它与q1中代价最小(设代价为v)的兔子里匹配（如果没有了就直接放入q2，后面都不管）。
可能有之后的兔子抢夺这个洞，那么
原文：https://www.cnblogs.com/hehe54321/p/10715869.html
