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

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

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

相关推荐

迟缓的斜杠青年巴比Q了:简历被投过的公司卖出去了,我前两天遇到过更离谱的,打电话来问我有没有意向报班学Java学习,服了,还拿我学校一个学长在他们那报班学了之后干了华为OD当招牌
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

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