首页 > 其他 > 详细

Golden Tiger Claw,题解

时间:2020-05-11 09:07:40      阅读:63      评论:0      收藏:0      [点我收藏+]

题目链接

题目:

  技术分享图片

题意:

  找到和最小的两个序列a,b满足对于任意i,j有a[i]+b[j]>=c[i][j](矩阵c给出)。

分析:

  首先很容易看出来要使这题要用KM算法,为啥呢?因为要最小化an,bn的和,而KM算法就是干这个的,把c当成边权,处理出来的顶标就是a,b。顶标当然有a[i]+b[j]>=c[i][j],但是为啥是最优呢?因为他都匹配了没法更小了。

Golden Tiger Claw,题解

原文:https://www.cnblogs.com/wish-all-ac/p/12866809.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!