用户工具

站点工具


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