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

一些比赛的题解 文章被收录于专栏

一些比赛的题解

全部评论

相关推荐

能干的三文鱼刷了100道题:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务