苟且的狮子

题解

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1)

/ 注册

全部文章 / 题解（共2篇）

[AHOI2009]MINCUT 最小割

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

最小割唯一性判断最小割

2020-08-19

1 637

方格取数(2) HDU - 1569

网络流，最大权独立点集题意： ##分析：看到这一题，我的第一反应是二分图求最大独立点集。想要用HK算法干掉他。但是仔细一看并非如此，题目让球的是最大权独立点集。这就是完全不同的问题了。真正的解法推荐看论文：胡伯涛《最小割模型在信息学竞赛中的应用》，直接跳到第五部分读就行了。不得不感叹，真是巧妙...

网络流最大点权独立集最小割

2020-08-14

1 911