BZOJ 4443 [Scoi2015] 小凸玩矩阵

发布于 2017-08-16  124 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4443

题意:一个 N*M 的矩阵,从其中选出 N 个数,其中任意两个数字不能在同一行或同一列,想知道选出来的 N 个数中第 K 大的数字的最小值是多少。


挺有意思的题,首先行列限制是明显的二分图模型。

那么考虑转化题问,第 k 大即第 n-k+1 小。二分答案转为判定性问题,就可以直接跑二分图最大匹配了。

然而有一个小问题,跑到了 n-k+1 个比答案小的数不代表能找到 k 个比答案大的数啊,所以跑出来的答案可能不合法?

实际上不是,因为能不能找到 k 个比答案大的数这个限制是随着 ans 越小就越松的,因为比它大的数更多了。

所以如果数据合法,找到的 ans 一定是合法的,否则就找不到一个 ans。

所以就跑的飞起了... 能加时间戳的地方都打了时间戳,还是跑不过网络流啊 T.T

 


一个非常弱的准退役OIER