2021牛客暑期多校训练营5 J. Jewels(KM模板)
Jewels
https://ac.nowcoder.com/acm/contest/11256/J
Description
打捞 个货物,货物会动,每一个时刻只能打捞一个,货物会动,打捞的代价是三维空间上的距离平方。
Solution
个货物只需要
时刻就能全部打捞,对于每个货物在每一个时刻都有相应的代价,可以构建二分图,左边是时刻,右边是货物,做带权二分图的最优匹配(KM算法)即可。
听说网上假的 KM 板子假的满天飞,于是偷了 roundgod giagia 的板子封装一下,以后我也有KM板子啦!
时间复杂度
Code
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48398426
一些比赛的题解 文章被收录于专栏
一些比赛的题解