Loading...
问题LeetCode LCP 04该题看上去与二分图匹配无关,但其实可以转化成二分图匹配。一个骨牌恰好覆盖两格,而这两格必须是相邻的。因此如果把相邻的两格...
问题洛谷 P3366最小生成树的模板题。之前用Kruskal解过LeetCode上针对边的问题。这次用Prim算法解决。解决标准的Prim算法不再赘述。其...
问题LeetCode #1489本题其实就是三个问题。求最小生成树、不含某条边的最小生成树(可能有也可能没有),一定含某条边的最小生成树。详细分析可见Le...
引入离散教材上讲过关键路径。其中,在求最长路径时,第一步是对节点进行“重新标号”。经过查阅,发现这个步骤其实叫做“拓扑排序”。很容易知道,如果一个图可以拓...
问题LeetCode #787在单源最短路径问题的基础上,加一条限制,最多只能通过K个点中转,或说最多只能通过K+1条边。解决除了Dijkstra之外,还...