qqz 发表于 2014-8-14 20:48

请会KM算法的大神解释下顶标是什么意思？

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