求问面试中遇到的疑似np-hard问题

有一个p行q列的矩阵,其中q>p,矩阵元素是数字,现在需要从每一行中各找出列索引不同的1个元素,使这p个元素之和最小。

换句话说,从p×q的矩阵里找出和最小的p个元素,其中这些元素各自的行和列都不相同。
全部评论
应该是二分图的最小权匹配,用费用流或者KM算法可以解,应该不是np-hard
点赞 回复 分享
发布于 2023-06-25 22:37 浙江

相关推荐

不愿透露姓名的神秘牛友
06-23 18:33
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

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