拓扑差分约束学习笔记
拓扑排序学习笔记
来自\(\color{Gray}\texttt{SharpnessV}\)的省选复习计划中的拓扑/差分约束。
简述
对一个DAG进行拓扑排序，是将DAG中所有顶点排成一个线性序列，使得DAG中的任意一对点\(u\)和\(v\)若\(
对一个DAG拓扑排序的结果可能不是唯一的。
Code
去下面随便找一道题的Code吧。
例题1
P1983 [NOIP2013 普及组] 车站分级
火车必须停靠等级大于等于火车等级的车站，就不会停比它等级低的车站。求最高等级的车站。
大于等于的关系不太好处理，但是小于的关系可以很方便的处理出来。
我们建一张图，从所有要停靠的站连向要停的站表示前者的等级要高于后者。然后拓扑排序。
注意这道题别用邻接表。
Code
例题2
P1038 [NOIP2003 提高组] 神经网络
这道题更模板了，直接拓扑排序同时处理每个点的\(c\)就好。
注意一些小细节，比如\(\ge0\)之类的条件。
Code
例题3
P7113 [NOIP2020] 排水系统
先拓扑排序，写个分数类，然后按照题目模拟即可。
用\(\operatorname{long long}\)的话只有\(60pts\).
Code
例题4
P7077 [CSP-S2020] 函数调用
有一个长度为\(n\)的序列，\(m\)个操作，操作有如下三种：
- 单点加
- 全局乘
- 以一定顺序调用其他操作，保证不直接或间接调用自身
如果没有操作3，那就倒着扫，打一个全局乘法标记，对于之前的每个加法，也乘上标记即可。
对于操作3，函数调用形成了一个DAG。
以及，如果某个函数在调用后序列被乘以\(k\)，相当于这个函数被执行了\(k\)次。所以操作2\3可以转化为操作1的执行次数。
通过以上的转化，这道题就变成了纯拓扑排序了。
Code
例题5
CF1476E Pattern Matching
\(\color{white}噢，对，其实这就是IV的题解\color{gray}awa\color{white}只有IV这样强的人才会写这么难的题目！\)
观察一下发现\(k\)很小。
所以对于给定的\(m\)个串，最多只有\(2^k\le16\)个模式串与之匹配。
对于每个给定串，限制条件可以转换为与之匹配的串中，指定某个串必须排在其他串前面。
这显然是图论拓扑模型，并且边数不会超过\(2^k\times m\)。
我们只用快速找出与之匹配的串，这可以用\(\texttt{Trie}\)树快速解决，下划线可以当作一个通配符插入。
时间复杂度\(\rm{O(2^km+kn)}\)，空间复杂度\(\rm{O(27kn+2^km)}\)。
Code
例题6
P3953 [NOIP2017 提高组] 逛公园
当然先求最短路，设\(f[k][x]\)表示松弛了\(k\)次的\(dis[x]\)。
可以得到\(f[k][x]\Rightarrow f[k+w+dis[x]-dis[v]][v]\)，其中\(k+w+dis[x]\)是这一次走到\(v\)的减去原来最短路\(dis[v]\)就是\(v\)的松弛的步数。由于最短路的性质，\(w+dis[x]-dis[v]\ge 0\)所以这个\(dp\)的转移实际上形成了一张分层图。我们可以从小到大枚举\(k\)可以保证转移有序。
要注意需要判断一种\(w+dis[x]-dis[v]=0\)的情况(简称0环)的情况。如果有\(0\)环且不合法\(dis_1[i]+dis_n[i]\ge dis_1[n]+K\)，那么方案数一定是正无穷种，输出\(-1\)。否则的话这个\(0\)环不会出现在转移的点中，可以不用管他们。
Code
差分约束学习笔记
来自\(\color{Gray}\texttt{SharpnessV}\)的省选复习计划中的拓扑/差分约束。
简述
将很多对变量之间的差\(\le c\)的关系转化为图论，再用图论算法来求解这个不等式组的解。
步骤
对于\(x_j-x_i\le k\)，我们会发现它类似最短路网络中的三角不等式\(d_v-d_u\le w_{
在建图的过程中要先关注具体问题，若求的是两个变量差的最大值，那么将所有不等式转变成"<="的形式并且在建图后求最短路，反之在转换成">="的形式，并且求最长路。
另外，如果有负环，那么该不等式组无解。我们只要放心大胆的跑SPFA就好。如果一个点入队次数大于\(n\)，说明存在负环。
Code
见模板题
例题1
P5960 【模板】差分约束算法
模板题，照着上面做就好。
Code
例题2
P3275 [SCOI2011]糖果
- \(A=B\Rightarrow A\le B+0\bigvee B\le A+0\)，连一条 \(A\leftrightarrow B\) 权值为 \(0\) 的双向边。
- \(A
- \(A\ge B\Rightarrow B\le A+0\)，连一条 \(A\to B\) 权值为 \(0\) 的边。
- \(A> B\Rightarrow B\le A-1\)，连一条 \(A\to B\) 权值为 \(-1\) 的边。
- \(A\le B\Rightarrow A\le B+0\)，连一条 \(B\to A\) 权值为 \(0\) 的边
因为每个小朋友的糖果数当然是正数，所以将每个\(dis\)加上\(min{dis}+1\)即可（至少也要有一颗糖）。
但是这样是正确的嘛？并不是，因为最短路跑出来会让最小的\(dis\)越小越好，并不满足要求的至少需要准备的糖果数。
从最短路改成最长路，只需要把边的方向和权值全部反过来，在SPFA的三角形不等式中改为if(dis[v]
注意超级原点和其他点的连边权值应为1，这样可以使得\(min{dis}=1\).（当然，把答案直接加上\(n\)也行。）
Code
如果你被卡了，不妨看看这个
这道题也可以用缩点+拓扑排序做，留作思考。
Code
例题3
P1250 种树
问满足指定区间\([l,r]\)内至少要种\(x\)棵树的条件下至少要种多少棵树。
对于每个约束条件可以变成\(sum_y-sum_{x-1}\ge c\).
同时因为每个点只能种一棵树，所以\(0\le sum_x-sum_{x-1}\le1\).
Code
例题4
SP116 INTERVAL - Intervals
从\(0\sim50000\)选出最少的数，使每个区间至少有\(c\)个数被选。
这是求最小值，所以将所有的不等式转换成">="的形式。
对于每一个约束条件，可以看成\(sum[b_i]-sum[a_i-1]>=c_i\).
由于每一个数只能选择一次，\(0\le sum_x-sum_{x-1}\le1\).
注意这里下标是从\(0\)开始的，所以就全部\(+1\)就好。
最后，多测不清空，抱玲两行泪。
Code
例题5
P4926 [1007]倍杀测量者
若一个选手的分数不满足
- \(S_a>S_b\times k_i\)
- \(S_a>S_b\times \dfrac1{k_i}\)
则他要女装。
要你求最大的正实数\(T\)使得在条件变为：
- \(S_a>S_b\times(k_i-T)\)
- \(S_a>S_b\times \dfrac{1}{k_i+T}\)
二分答案\(T\)。对限制条件进行连边：
-
设\(S_0=1\).
-
对于\(S_a>S_b\times k_i\)，连一条\(B\to A\)权值为\(k_i\)的边。
-
对于\(S_a=x\)，连一条\(0\to A\)权值为\(x\)的边，连一条\(A\to 0\)权值为\(\frac1x\)的边。
将这张图跑乘积最长路。
如果有环的话说明无法同时满足所有的不等式，也就是说明一定有人要女装啦！\(\color{white}ps:\texttt{lxl}女装真好看！\)
Code
例题6
P5590 赛车游戏
给一张有向图，请给每一条边赋上边权\(w\in[1,9]\)使得每一条\(1\to n\)的路径的长度相等。
如果始终想的是如何让所有\(1\to n\)的路径相等那么就想错方向了。
在一个图中进行最短路的时候，\(dis_x+w_{x\to v}=dis_v\)说明\(dis_v-dis_x=w_{x\to v}\in[1,9]\)，这样我们才可以用差分约束系统进行求解。
\(1\le dis_v-dis_x\le9\longrightarrow dis_v\le dis_x+9\bigvee dis_x\le dis_v-1\)，所以我们连一条\(x\to v\)权值为9的边，一条\(v\to x\)权值为\(-1\)的边。
Code