首页 > [AHOI2009]MINCUT 最小割
开通博客写题解
头像 __故人__
发表于 2020-09-22 20:19:19
分析 主要考察最小割的性质。我们发现如果一条边是可行边，那么一定要满足以下性质。 满流，没有第二条增广路 。考虑证明，如果没有满流，那么我们完全没必要割去这条边。如果有，那么证明这个路径还可以继续增广，不满足最小割的定义。那么如果一条边是必须边。 满流，直接链接 所在集合。这里考虑最小割的定义 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 苟且的狮子
发表于 2020-08-19 21:06:06
结论题，最小割，tarjan 题意： 分析： 题目看了，就是让我们对图中的每一条边都做判断：是否可以是最小割边？是否一定是最小割边？暴力做法：n*m对于每一条边我们都单独判断！ 那么现在来看tarjan做法：首先让我们想想，传统如何判断一条边能不能在最小割集中。先跑最大流，得到其残余网络(此残余 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”