LOJ6405 「ICPC World Finals 2018」征服世界
LOJ 分析 考虑反着看整个过程，那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞，所有老鼠都必须进洞。 $u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$，每次把儿子的堆合并，然后取堆顶匹配，再把反悔操作加入堆中即可。 然而这样并不能保证所有老鼠都进洞，所以我们把老鼠...
LOJ 分析 考虑反着看整个过程，那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞，所有老鼠都必须进洞。 $u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$，每次把儿子的堆合并，然后取堆顶匹配，再把反悔操作加入堆中即可。 然而这样并不能保证所有老鼠都进洞，所以我们把老鼠...
UOJ 分析 这个东西相当于洞有容量上限和额外代价，因此可以考虑模拟费用流。 我们维护两个堆，分别代表洞和老鼠，然后从左往右扫 如果当前是老鼠，取出一个代价最小的洞，代价即为 $x+cost$；后面有可能反悔，即让右边的一个洞匹配这只老鼠，所以要向老鼠堆中加入 $-(x+cost)-x$。 如果当前是洞，取出一只代价最小的老鼠，代价即为 $y+cost+w$；后面有可能反悔，即让右边的一只...
Luogu LOJ 分析 至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。 考虑一个费用流模型，即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边，从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边，从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边，再新建两个点 $C,D$，从...