感觉最近学的东西有点杂，最近复习了一下之前学习的匈牙利算法，突然发现，匈牙利算法解决的二分图问题竟然不只有二分图最大匹配问题！这篇Blog，我就来讲解一下匈牙利算法所解决的常见的四种模型吧！ 什么是二分图 就是对于一个图中的所有点，都可以分类两个到集合X和Y，使得所有的边关联的两个顶点，恰好一个属于集合X，另一个属于集合Y。换句话说，就是集合X中任意两点间没有连边，集合Y中任意两点间也没...
GDOI Cu滚出了好难受啊QwQ。今天早上目送完参加Day3的大佬后，就去听了中大严紫熙的《网络流的沧海一粟》，收获良多。现在我们就来简单介绍一下简单的网络流算法和一些推论和经典技巧吧！ 什么是网络流问题 我们最常见的问题是最大流问题： 问题表述：给定一幅图（n个结点，m条边），每一条边有一个容量，现在需要将一些物品从结点s（称为源点）运送到结点t（称为汇点），可以从其他结点中转，求最...
上篇博客我们重点讲解了tarjan算法的实现以及它最重要的用法——求解强连通分量。这篇博客我们就继续学习一下tarjan的其他经典用法。 运用tarjan求割点 什么是割点 在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point） 例如，在下图中，0、3是割点，因为将0和3中任意一个去掉...
终于到图论部分了，图论我是真心弱啊QwQ。今天复习了一下tarjan，总结了一下其基本用法，希望对你有帮助吧。 什么是tarjan？ tarjan算法又称“塔尖”算法，是解决图联通问题的一种神奇算法。换句话说，tarjan就是基于DFS算法，对每个点进行标记处理的一种基本图论算法。 tarjan有什么用？ 由于tarjan是解决图联通的一种算法(:з」∠)，所以我们很自然的可以想到可以用...