Gravatar
yrtiop
积分:2101
提交:309 / 808

Pro3843  [SDOI 2017] 新生舞会

合格的签到题。

首先发现式子是一个 0-1 分数规划的模型,所以先二分答案 $mid$,男生 $i$ 和女生 $j$ 配对的价值为 $a_{i,j}-b_{i,j}\times mid$。

进一步地,发现男生和女生的关系形成一张二分图,并且男女双双配对,配对有权值,相当于二分图带权最大完美匹配。

可以使用 KM 算法求解,但我不会,学了一个费用流打了一下。核心思想就是把 EK 算法的 BFS 找增广路改为 SPFA 找增广路,顺便求一下最长路。

时间复杂度 $\mathcal O(n^4)$,在 COGS 的机器上可能有点难跑,但这只是理论上界,而且这可是二分图,SPFA 和 EK 都很难卡满,足以通过本题。


2023-03-10 22:10:09    
我有话要说
暂无人分享评论!