几天前又看到 Skh juju 在切紫题……我深刻感受到了我的弱。
我意识到本就咸鱼的我如果再不学习，可能就永无翻身之日了……
于是我开始和 Skh juju 一起看这道紫题。结局很显然，蒟蒻 Nanjo_Qi 在 70 分被卡了好久好久，到最后还是对着题解发现了 2 处细节错误……
做完之后 Skh juju 早就已经开始等待放学吃饭并用“你刚刚做完啊”的眼神看着我。
被虐打的我只能默默对着题解学习一个，看看其他的思路，于是似乎发现了一些让我感兴趣的东西——分层图。
最短路最长路？最大流费用流？对于各位 dalao 似乎只是一个板子的事情。
就算需要复杂的建模分析重构图，人生经验丰富的各位也能分分钟切掉它。
Emmmm……可是假设在最短路和网络流的基础上增加一些干扰操作呢？
比方我们能够进行一些操作，让图中某些边的边权或者容量减半，而这些操作不是预先给出的，而是需要我们自己选择一些边进行操作，又该怎么做呢？
非常显然对于这种情况，生搬硬套普通的算法是没有办法处理的，而是需要一些技巧处理一下——这就用到了分层图的思想。
所谓分层图，就是状态是多维的一个巨大的图。正常的算法是在一个二维的图中进行的，而用到分层图的时候就须要在多维空间内进行。
通常情况下需要用到分层图思想的题目都有一些干扰操作，且次数不多。我们对这些干扰操作的解决方法就是把原图“复制”，并且一般来说干扰操作有多少次就要复制多少。这样，一个新图为一层，往往还要在层与层之间连边，就形成了形象的分层图”。
分层图只是一个技巧，而且也不是那么难。
通过一个例子理解一下。比如，求最短路问题，可以免费通过 k 条边。则除了原图外再建 k 层图，然后对于每一条边，连一条从此点到下一层的这条边所对应的终点 的，层与层之间的边，边权为零。那么从一层到下一层就相当于走了一条免费边。
由于不需要走完所有的免费边，所以应取所有层的终点的最短路的最小值。
同理，其他问题也可以类比解决。
可见，存图的数组需要开得充分大，由于还要连跨层边，所以 maxn * (maxk + 1)是远远不够的。
大概以后有什么新的发现的话还会再补充吧，如果有错误或者针对以上的优化请务必告诉我qwq！
放几道题目吧：
[USACO15JAN] Grass Cownoisseur
—— 用你的笑容去改变这个世界，别让这个世界改变了你的笑容。