[问题求助] 请会KM算法的大神解释下顶标是什么意思？

[复制链接]

字体大小: 正常放大

qqz

2 主题	11 听众	49 积分

升级 46.32%

TA的每日心情

	衰 2014-8-29 23:15

签到天数: 10 天

[LV.3]偶尔看看II

自我介绍: 小白一枚，希望大家多多指教

群组: 国赛讨论

电梯直达

1^#

发表于 2014-8-14 20:48 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。
以上是概念，很不理解顶标是什么？为什么可以加。A[i]+B[j]表示的是什么？
谢谢大家！

zan