这一篇是算法的网3的下一篇。
观前须知：
1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。
2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。
——————————————————————————————————————————
这是我们的网现在的样子：
我们接着上一篇提到的，来讲一讲旅游巴士的第二种做法。
喔喔喔喔喔喔喔。我有点恍然大悟了。
分层图本身可能比不是一定要把每个点都以在图上添加k个来实现的。（比如说P4568飞行路线）
它也可以是：一个点有k个状态。
而dis[i][j]就是表示第i个点的j个状态。
这是我上一篇写的：
它的第二维就是状态。虽然是n个点，但实际上是k*n个点的分层图。
哦。所以没有第二种做法。
原来如此。
好的，那我们看下一题吧。
陌路寻诗礼
唔。我好像没见过这种要求。好神奇啊。
这道题目的要求是：给出n（节点数）,m（边数）,k（边权取值范围）和m条边。
问：如何安排m条边的边权，使得从点1到其他城市的最短路径为1.
我的初步思路是跑BFS，然后在跑的过程中给边加边权。
那么如何赋值边权呢。
我不会。
啊啊啊啊。怎么构造啊。
想太久了没想出来又去看题解了。我觉得我好**。但关键是不看也做不出来。
怎么办啊。
那我多做一点最短路绿好了。我觉得只练十题太少了。练二十题好了。
牛的旅行
社交网络
道路选择
最长距离
黑暗城堡
(上面的这些是前面的十多题遗留的，下面的十题是新选择的）
团
图上交互题
car的旅行路线
最优贸易
灾后重建
房间最短路问题
跑路
Cleaning Shifts S
电话
采蘑菇
好的，题挑完了，我们接着看陌路寻诗礼。
好的，我看完题解了。
其实这个题解让我感觉很诡异：就是我觉得，这个思路似乎是不难想的，或者说理所应当的。但是同时我认为，这个做法像是从天上掉下来的一样。（也就是我当时在想题的时候，从来没有想过这个方面）
它居然是可以直接加的嘛……好震惊。
我再看完之后的感觉是很奇怪，因为在我的大脑里潜意识认为这种做法行不通的。（如果有大佬知道这是怎么回事，欢迎指点qwq）。
而且，这道题目的代码实现也非常非常地简单！
只要在原有的模板上做一点点更改就好了：
我不会告诉你我调了半个小时就因为
并且，可喜可贺的是在我调错的时候，我重新搞懂了这个思路，我明天来分析它！
好吧。我突然奋发图强了。所以我今天晚上就来分析它。
这个题解的楼主给你的感觉是：四两拨千斤。
但是实际上它很复杂。接下来我会从两个角度去分析：
一.文字本身
这句话看似普通又平常，但是想到它其实并不容易哦。
当你一开始做的时候，需要给每条边去赋值。你可能就得想：欸，我是要赋值最大值还是要赋值最小值，或者是中间值？（甚至如果你想的偏一点，你甚至可能根本想不出要赋值，可能回去想一些乱七八糟的方法，构造题本身就很容易很容易跑偏）
有一个突破口可以（更容易）想到它：
当k只能等于1，那么就直接赋值为1，然后融入一部分最短路计数的代码，去看有没有相同值。
这部分做完之后，你再去看接下来怎么做，就会更容易联想到。
接下来的部分我会从代码的角度去分析：
我上面的那版代码，是我已经更具这份题解提供的代码修改过的。
我现在将两份代码（我原来的和我现在的）进行对比。
现在的：
原来的：
接下来，我们一处对比一处对比地分析一下：
1.我将len变量删除了
并且把要加的len改成了"+1"。
这是因为，在dijkstra中，每条边能够对它所连接的点进行更新的机会永远都只有一次。
(因为每个点在Dijkstra里面也只会被遍历一次）
而第一次被遍历时，这条边的初始值也只能是1。
2.直接填写2
这边的逻辑和上面的逻辑是一样的。直接增加1就好了。
虽然我前面那些都写得很简单很轻松，但是其实头脑风暴了很久。
所以在这里得建议是：大家做完一道题之后可以去看看题解写的代码。有一些代码写的简短漂亮，那么它背后的思路可能也更好。
我当时发现后面可以直接填2得时候我都惊呆了。好妙得构造啊。
这道题我一直没有注意道德是：在dijkstra中，每条边只会进行一次遍历（单向边哦）。
不过这个也是只在模板上进行更改，并没有与算法进行美妙的联动。但是思想上有提升。
所以网没办法更新qwq。
好吧，我们看下一题吧。
采蘑菇
五一新学了最小生成树。八级要考。先过一点最小生成树。
二.最小生成树
例题：买礼物
先说做法，再说想法。
做法：有优惠，一件礼物作为一个顶点，价格为边。建立零点，将零点与其他每个顶点连边，代表原价购买此商品。
由于在熟悉，所以prim和kruskal都会拿出来弄一遍。
prim:
在写prim的时候，我发现了一点比较有意思的事情。
我将vis[k]=1改动成了：
如果加在了这里，那么如果后续我还能用别的边来优化dis，就优化不到了。
当时居然没注意，随意改了一下酿成大错qwq。
接下来是kruskal的版本。
分析：
1.如何分析这道题目需要用到最小生成树
分析这个问题，先需要想到，这是一道和图论相关的问题。
如何将一个实际问题转化成为图。或者说如何识别有“图”。
它有点之间的关系。点i和点j之间的联系就是k[i][j]。
那么这个联系就可以变成边。
想在图论相关的题目中找”最小“。那么一般考虑：最短路，最小生成树，树形dp(我对树形dp不太了解，但应该也是相关）。
然后再看，这道题目需要求取整个图的所有边权。比较容易想到最小生成树。
最后分析复杂度：一共有n*n条边。大约2e5。可以支撑的起O(mlogn)的时间复杂度。
2.使用prim更好还是使用kruskal更好。
稠密图。推荐使用prim。
营救
找最小生成树。再计算出点s到点t的最大值即可。
天空
灌溉
