nagisa_菜鸡

题解

/ 注册

全部文章 / 题解（共3篇）

追债之旅解题报告(最短路变形)

这道题算是一道分层图的最短路：按照天数对图进行分层，并且，在day-1层和day层，每个相连的节点(u,v)都有一条权值为w[day]的边，表示从day-1天在u到day天到v需要w[day]的路费。这样考虑的话，我们可以把每个节点拆成k个，然后每个节点u的第day-1个连到v节点的第day个，边权...

每日一题图论

2020-08-07

0 516

小A的最短路解题报告(LCA,最短路)

首先，题目有个条件：n个节点，n-1条路径，所以，这是一棵树。之后，会再在u,v之间加入一条边权为0的边，让我们求图上任意两点的最短路。若我们忽略新加入的uv边，那直接求lca求距离就行了。但是，现在加入了uv边，但是，我们可以想到，如果真正的最短路径不经过uv边，那么答案依旧还是lca求得的结果，...

每日一题图论

2020-08-01

0 745

[SCOI2012]滑雪与时间胶囊结题报告（最小生成树）

看到这道题，发现不会最小生成树，遂昨晚熬夜补了prim算法，今天来写这道题。看到时间胶囊能回溯，因此确实可以想得到是最小生成树，其实就是最小生成树后求路径长度和最小的问题。这道唯一特别一点的地方就是只能从高处到低处，并且要保证能去的地方最多，所以贪心策略需要加一条：以边终点高的优先选择，保证高度高（...

最小生成树每日一题图论贪心

2020-05-04

0 656