首页 > [AHOI2009]MINCUT 最小割

__故人__

发表于 2020-09-22 20:19:19

分析主要考察最小割的性质。我们发现如果一条边是可行边，那么一定要满足以下性质。满流，没有第二条增广路。考虑证明，如果没有满流，那么我们完全没必要割去这条边。如果有，那么证明这个路径还可以继续增广，不满足最小割的定义。那么如果一条边是必须边。满流，直接链接所在集合。这里考虑最小割的定义展开全文

苟且的狮子

发表于 2020-08-19 21:06:06

结论题，最小割，tarjan 题意：分析：题目看了，就是让我们对图中的每一条边都做判断：是否可以是最小割边？是否一定是最小割边？暴力做法：n*m对于每一条边我们都单独判断！那么现在来看tarjan做法：首先让我们想想，传统如何判断一条边能不能在最小割集中。先跑最大流，得到其残余网络(此残余展开全文

查看本题

查看本题讨论

等你来战

查看全部