题解 CF1450E Capitalism

· · 题解

个人认为不能算作差分约束题，只不过是一道最短路应用的题目罢了，如果参照第一篇题解的说法差分约束这么建边只能保证不等式 |a-b| \leq 1，这并不能作为 |a-b| = 1 的充要条件。

考虑将边加成双向边，如果已经确定了从属关系那么连边 (a,b,1) , (b,a,-1)，否则连边 (a,b,1),(b,a,1)。

之后我们跑全源最短路，处理原图中是否有奇环后即可判断是否有解，因为一出现奇环你这些边怎么赋值都不会有解。

具体而言，我们枚举源点 s 后枚举所有连边，考虑到判断奇环只用判断路径长度的奇偶，设 dist_{a,b} 表示 a 到 b 的最短路，对于任意边 (u,v) 若出现 dist_{s,u},dist_{s,v} 的奇偶性相同，加上 (u,v) 之间的边就出现了奇环，这时候直接判无解就好了。

当然可能会出现 s -> x 有多种路径的情况，不过由于我们只判断奇环是否出现，所以如果当前枚举的最短路并不是两个同奇偶的路径并且存在同奇偶的路径，说明存在其他的用最短路判断是奇环的奇环影响了这个环用最短路判断出来不是奇环，那么说明另外那个奇环就能找到了。（这里建议再画一下图）

当然这里的讨论要排除 dist_{s,u} 和 dist_{s,v} 互相更新的情况，因为权值是 1 所以这里肯定不会影响判断奇环，自然也不再讨论范围之内。

（这里当然建议大家直接二分图染色判奇环就行了，这个东西只是由于此题已经判了全源最短路所以一种更顺手的做法）

接着就是寻找一个合法的极差最大序列，那就是极小化最小值极大化最大值。枚举源点设其为 0，那么由于跑的最短路本身就是最小值所以最小值一定能被构造出来，而对于最大值，肯定不能超过源点出发中最大的最短路，比如说 3 -> 5 有两条路径一条长为 3 一条长为 4，对于第一条路径全取 +1 顶破天了也就 3 不可能达到 4。

这样做之后由于你本身是用最短路来限制的，所以最短路上的值每个点肯定都取得到，所以最后的答案就是枚举每个点作为源点可以得到的最大极差。

时间复杂度 O(n ^ 3)。