Articles in the category of 技术杂烩

  1. Home
  2. 技术杂烩

二分图匹配之匈牙利算法

问题LeetCode LCP 04该题看上去与二分图匹配无关，但其实可以转化成二分图匹配。一个骨牌恰好覆盖两格，而这两格必须是相邻的。因此如果把相邻的两格...

  • Colin
  • June 29, 2020
  • No comments
    •

    最小生成树之Prim算法

    问题洛谷 P3366最小生成树的模板题。之前用Kruskal解过LeetCode上针对边的问题。这次用Prim算法解决。解决标准的Prim算法不再赘述。其...

  • Colin
  • June 27, 2020
  • No comments
    •

    最小生成树之Kruskal解法与并查集

    问题LeetCode #1489本题其实就是三个问题。求最小生成树、不含某条边的最小生成树（可能有也可能没有），一定含某条边的最小生成树。详细分析可见Le...

  • Colin
  • June 26, 2020
  • No comments
    •

    拓扑排序与关键路径

    引入离散教材上讲过关键路径。其中，在求最长路径时，第一步是对节点进行“重新标号”。经过查阅，发现这个步骤其实叫做“拓扑排序”。很容易知道，如果一个图可以拓...

  • Colin
  • June 25, 2020
  • No comments
    •

    经过指定边数的单源最短路径

    问题LeetCode #787在单源最短路径问题的基础上，加一条限制，最多只能通过K个点中转，或说最多只能通过K+1条边。解决除了Dijkstra之外，还...

  • Colin
  • June 24, 2020
  • No comments