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

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

一些比赛的题解

全部评论

相关推荐

点赞 评论 收藏
分享
野猪不是猪🐗:这种直接口头上答应,骗面试,面完了直接拉黑,相当于给自己攒面经了(
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务