差分约束

第十四次CCF-CSP 第二题买菜原题链接：3263. 买菜 - AcWing题库思路分析简单来说，就是给出两组区间的集合A,B 求出两集合中相交区间的部分的长度，注意若区间 [s,t] 是相交的，则长度为 t-s 。思路一因为数据量比较小&am…

题目给定 n 个区间 [ai,bi] 和 n 个整数 ci。你需要构造一个整数集合 Z，使得 ∀i∈[1,n]，Z 中满足 ai≤x≤bi 的整数 x 不少于 ci 个。求这样的整数集合 Z 最少包含多少个数。输入格式第一行包含整数 n。接下来 n 行，每行包含三个…

【差分约束】洛谷P1993 小K的农场题解题目传送门分析一看题目就知道可以把条件转换成不等式，然后使用差分约束求解。差分约束可以自行百度OR谷歌。可以把建边为w(a,b) c， 转换成 ，建边为w(b,a) -c。然后使用dfs优化的spfa跑一个最…

1.求最大值，用最短路，不等式转化成 a < b c形式，从b向a建立权值为c的边g[b].append((a,c)) 2.求最小值，用最长路，不等式转化成a > b c形式，从b向a建立权值为c的边 import sys from collections im…