BZOJ 4276 [ONTAK2015]Bajtman i Okrągły Robin

发布于 2017-07-01  267 次阅读


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

题意:有 n 个强盗,其中第 i 个强盗会在 [a[i],a[i]+1],[a[i]+1,a[i]+2],...,[b[i]-1,b[i]] 这么多段长度为 1 时间中选出一个时间进行抢劫,并计划抢走 c[i] 元。你在每一段长度为 1 的时间内最多只能制止一个强盗,那么你最多可以挽回多少损失呢?


强行费用流边数是\(n^2\) 级别的.... 如果线段树优化建图的话是\(nlog_n\) 级别...

显然时间复杂度都很虚

有一个很巧妙的贪心做法,实际上此题需要求一个二分图最大权匹配,对于一般的题目:按权排序后贪心匈牙利是不行的,考虑什么情况会卡掉这个做法:当且仅当为小权值找匹配的时候把已经匹配的大权值换掉了。

然而此题不会有这种情况,因为一个强盗连出去的边权值都是相同的,大权值不会换的更小,那么\(O(n^3)\) 的匈牙利就跑的飞起了

 


一个非常弱的准退役OIER