2020-2021:teams:farmer_john:差分约束
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:差分约束 [2020/05/27 18:16] jjleo [建边方法] |
2020-2021:teams:farmer_john:差分约束 [2020/05/31 18:51] (当前版本) 2sozx [倍杀测量者] |
||
|---|---|---|---|
| 行 14: | 行 14: | ||
| * 另一道例题：[[http://poj.org/problem?id=1716|POJ 1716]] | * 另一道例题：[[http://poj.org/problem?id=1716|POJ 1716]] | ||
| =====建边方法===== | =====建边方法===== | ||
| - | * 考虑松弛过后的最短路$dis$数组，对任意一条长度为$k$从$x$到$y$的有向边，满足$ dis_y \le dis_x + k $，移项得到$ dis_y - dis_x \le k $，这与开头提到的$ x_i - x_j\le k $神似。因此我们将每个变量看成一个点，对每个不等式$ x_i - x_j\le k $连一条从$x_j$到$x_i$的长度为$k$的有向边即可，若图存在负环，意味着通过不等式相加可以得到自己小于自己，那么显然是无解的，否则一定有解，因此判负环即可。 | + | * 考虑松弛过后的最短路$dis$数组，对任意一条长度为$k$从$x$到$y$的有向边，满足$ dis_y \le dis_x + k $，移项得到$ dis_y - dis_x \le k $，这与开头提到的$ x_i - x_j\le k $神似。因此我们将每个变量看成一个点，对每个不等式$ x_i - x_j\le k $连一条从$x_j$到$x_i$的长度为$k$的有向边即可。若图存在负环，意味着通过不等式相加可以得到自己小于自己，那么显然是无解的；否则既然这个图不存在负环，那么我们通过最短路算法一定可以松弛所有点使得$dis$数组满足我们附加的条件，因此一定有解。 |
| * $x_i - x_j \le k$，则连一条从$x_j$到$x_i$的长度为$k$的有向边。 | * $x_i - x_j \le k$，则连一条从$x_j$到$x_i$的长度为$k$的有向边。 | ||
| * $x_i - x_j \ge k$，即$x_j - x_i \le -k$，连一条从$x_i$到$x_j$的长度为$-k$的有向边。 | * $x_i - x_j \ge k$，即$x_j - x_i \le -k$，连一条从$x_i$到$x_j$的长度为$-k$的有向边。 | ||
| * $x_i = x_j$，等价于$x_i - x_j \le 0$且$x_i - x_j \ge 0$，连一条从$x_i$到$x_j$的长度为$0$的无向边。 | * $x_i = x_j$，等价于$x_i - x_j \le 0$且$x_i - x_j \ge 0$，连一条从$x_i$到$x_j$的长度为$0$的无向边。 | ||
| * 最后，额外建立一个起点，向每个变量连一条权值为$0$的边，如果有解，最终$dis$数组中的取值就构成了一组可行解。 | * 最后，额外建立一个起点，向每个变量连一条权值为$0$的边，如果有解，最终$dis$数组中的取值就构成了一组可行解。 | ||
| + | =====放题===== | ||
| + | ====[SCOI2008]天平==== | ||
| + | [[https://www.luogu.com.cn/problem/P2474|传送门]] | ||
| + | * 题意：$n$个重量范围已知的砝码，部分轻重关系已知，先在天平左侧放两个砝码，求任选两个砝码使天平向左倾/水平/向右倾的方案数 | ||
| + | * 题解： | ||
| + | * 由于只知道轻重关系，考虑用$dmax[i][j]$记录$i-j$的最大值，最小值同理。 | ||
| + | * 建出来之后不难发现，和$floyd$求最短路有点像欸 | ||
| + | * 于是用$floyd$跑一遍确定一下上下界，然后枚举两个砝码就行了 | ||
| + | ====[FJOI2018]所罗门王的宝藏==== | ||
| + | [[https://www.luogu.com.cn/problem/P4578|传送门]] | ||
| + | * 题意：有 $n+m$ 个变量，给定 $k$ 组限制，每次告诉你 $x_r+y_c=k$，问是否有可行解。 | ||
| + | * 题解：将 $x_r+y_c=k$ 转变为两个不等式 $x_r-(-y_c)\le k,x_r-(-y_c)\ge k$ 建边判负环即可。 | ||
| + | ====倍杀测量者==== | ||
| + | [[https://www.luogu.com.cn/problem/P4926|传送门]] | ||
| + | * 题意：已知某些位置的 $S_i$ ,求最大的 $T$ 使得存在一个序列 $S$ 满足 $m$ 个形如 $S_a>S_b\times (k_i-T),S_a>S_b\times \frac{1}{k_j+T}$ 的限制。如果不存在则输出 $-1$。序列长度 $n\le 1000$，限制个数 $m\le 1000$ | ||
| + | * 题解：将限制取对数，然后对于 $T$ 二分。建图的时候要将已经确定的 $S_i$ 可以建立两个形如 $S_0-S_i\le -S_i,S_i-S_0\le S_i$ 的限制即可，然后就可以判断是否有解。 | ||
| + | ====[HNOI2005]狡猾的商人==== | ||
| + | [[https://www.luogu.com.cn/problem/P2294|传送门]] | ||
| + | * 题意：给定 $m (m\le 1000)$ 个限定，每个限定为 $\sum_{i=s}^t a_i=v_j$，问是否存在这样一个序列 $a$。 序列长度 $n\le 100$ | ||
| + | * 题解：考虑前缀和 $sum_i=\sum_{j=1}^i a_j$ ，限定转化为 $sum_t-sum_{s-1}=v_j$ ，将等式转化为两个不等式 $sum_t-sum_{s-1}\ge v_j,sum_t-sum_{s-1}\le v_j$ 即可。 | ||
2020-2021/teams/farmer_john/差分约束.1590574567.txt.gz · 最后更改: 2020/05/27 18:16 由 jjleo
