标签: 最小割

1 篇文章

【整理】算法竞赛图论进阶学习笔记
图匹配 二分图匹配 判定 静态:黑白染色。 动态:分层并查集。并查集可以维护的可以是点的连接关系,也可以是关系的连接方式。连接两个点,我们可以改为连接这两个点的逻辑关系,黑-白,白-黑。如果有一天同一个点的黑白被连在了一起,则这就不是一个二分图。 分层并查集经典例题:P2024 [NOI2001] 食物链。 最大匹配:匈牙利算法 模版:P3386 …