切糕模型学习笔记

Solution. LG6054 开门大吉 / 切糕模型中对该模型的讲解已经比较完善，这里再做一些补充。

首先，再给出一种防止一条链上割多条边的方法。

考虑给每条边的费用加上一个 $\inf$，假如我们有 $n$ 个待决策的变量，按照预期，答案应该在 $[n\times \inf,(n+1)\times\inf)$ 之间，然而，如果割掉了限制或者一条链上割掉了多条边，求出的值都会大于这个范围，此时判定为无解。

我个人还是比较喜欢加反向边。这三种不同的打补丁的方法应该能够有助于深入理解切糕模型。

绝对值可以拆成两个不等式，直接建图即可。

其实很显然这题才是一般认为的该模型的起源，但是开门大吉相对更直接一些，所以借用那题来介绍这个模型。

接下来是一些更有意思的题目。

发射器

据说是 Topcoder 的题，但是不知道题号之类的，而且我也不用 Topcoder。

在地图上有 $n$ 个敌人，每个敌人有一个消灭可获得的价值。

地图上还有 $m$ 个发射器，每个发射器有最大的射程限制，同时有一个朝向（形如上下左右），保证没有面对面的发射器。

你可以对每个发射器指定一个射击距离，这个发射器就会消灭发射器朝向的这个方向的、距离恰好为这个射击距离的敌人，但是要求两个发射器射击时经过的格子不能相交。

求最多能消灭多少价值的敌人。

$1\le n,m\le 50$

对于一横一竖两个射程相交的发射器，假设他们选取的射程是 $r,s$，与交点的距离为 $a,b$，我们有：

此限制也可以用切糕模型描述。

在传统的切糕模型中，我们实际上是将一个限制拆成了一系列形如「若 $x_i\ge a$，则 $x_j\ge b$」的限制从而建图，注意到这里限制好像不等号方向有点问题，由于限制在横竖发射器间连边构成了二分图，所以将竖发射器链上的权值倒序排列即可。

注意上述两个限制是等价的，描述前者即可即可。

给出一张 $n$ 个点的连通有向图，可以任意加边。

设加边后从 $1$ 到每个点的距离为 $d_i$，给出数组 $D_i$，最小化 $\sum|D_i-d_i|^3$。

$1\le n\le 100$

最短路模型可以描述为：

现在已经存在若干限制，我们还可以任意添加限制，显然，在满足原有限制的情况下，我们可以将 $d_i$ 调整到任意我们期望的值。

只需要描述 $d_u+1\ge d_v$ 的限制即可，很显然这又是切糕模型。