胡马渐远蹄声尽，四顾萧条暮色起。
空城角随西风吟，废池乔木，犹厌言兵。——《无题》
luogu P6880
反转边等价于删一条再加一条边。
加边的肯定随便求。
删边，如果删在最短路上我们就暴力跑一遍；否则肯定还是最短路。两个方向最短路上 \(\mathcal{O}(n)\) 条边。用稠密图朴素 dij 复杂度 \(\mathcal{O}(n^3)\)。
arc107F
考虑先把所有点全删了，因为有绝对值，一个联通块的 \(b\) 贡献符号一定一样，把每个点拆成正负，考虑最小割，那就是说图上相邻点选不同号冲突。
两边都割掉代表不加，所以选了一边的贡献要加 \(a_i\)。
uoj605
可以给一个标签建一个虚点，令来回的边权都是 \(\frac{1}{2}\) 就行了。
然后每次考虑一个标签的点到所有点的距离。然后建出以这个虚点为起点的最短路 DAG，对于另外一个点 \(u\)，如果一个此标签的点 \(x\) 是 DAG 上 \(u\) 的前驱，那么说明 \(x\rightarrow u\) 的最短路长度是这个虚点到其的最短路长度 \(-\frac{1}{2}\)，否则说明 \(x\rightarrow u\) 需要先经过虚点，也就是 \(+\frac{1}{2}\)。
直接用 bitset 判前驱会炸内存，所以我们对于 bitset 的内部逐块处理，也就是 \(w\) 个为一组。因为我们对于每个颜色只需要在乎这个颜色的所有点到整张图的可达性，一共 \(n\) 个点，所以复杂度 \(\mathcal{O}(\frac{n(n+m)}{w})\)
P3327
每个位置有已知的多个决策，决策之间有简单限制，考虑最小割。
从源点到汇点建若干条链，每条链上有 \(R\) 个点，割掉其后的边表示选择对应的高度。
-
如何防止一条链割多条边？
对于所有链，反过来给相邻位置连权值 \(\infty\) 的边。因为如果你割掉至少两条边，说明最后两条边之间是可以被其他链到达的，反过来连边可以保证它也可以到达起点，然后就令前面那一堆都没有割的必要了。
SDSC2025 dwt 模拟赛放了个类似的题，从其上可以得到启发。
考虑两条链之间的边是什么个关系，对于两条链之间 \(u\rightarrow v\) 的边，表示了如果我选择了割第一条链的 \(u\) 之前的边，那第二条链割掉的边必须在 \(v\) 之后，如果我们对每个 \(u\)，给 \((a,u)\rightarrow (b,u-d)\) 连边，设两个点的决策是 \(x,y\) 那就是 \(y\ge x-d\)。反过来连一遍就是 \(|x-y|\le d\) 了。
未完待续。