小编Gib*_*ybo的帖子

假设我有两组:(n_1,n_2,...)和(m_1,m_2,...)和匹配函数匹配(n,m),它返回0到1之间的值.我想找到两组之间的映射,以满足以下约束:

• 每个元素在相反的集合中必须至多有1个匹配的元素.
• 不匹配的元素将与成本1的虚拟元素配对
• 应用于所有元素时匹配函数的总和是最大的
• 我无法正式表达这一点,但是如果你按照原始顺序排列每个彼此平行的组并在匹配的元素之间画一条线,那么任何一条线都不会交叉.Ex [n_1 < - > m_2,n_2 < - > m_3]是有效的映射,但[n_1 < - > m_2,n_2 < - > m_1]不是.

(我相信前三个是标准加权的二分匹配约束,但我指定它们以防我误解加权二分匹配)

这在指数时间(相对于集合的大小)进行穷举搜索是相对简单的,但我希望多项式时间(理想情况下为O((| n |*| m |)^ 3)或更好)解决方案存在.

我已经在"赋值问题"/"加权二分匹配"上搜索了相当多的数量,并且已经看到了具有不同约束的变体,但没有找到匹配的或者我能够通过这个添加的排序约束减少到一个.你有什么想法我可以解决这个问题吗？或者也许是在多项式时间内无法解决的粗略证明(对于我的目的,减少到NP-complete也会起作用)？

在C++中,通常的做法是在头文件中声明函数并在cpp文件中定义它们.这导致每个函数的原型总是有两个副本.然后,每当我想要更改函数的名称/返回值/参数时,我必须在两个文件中手动更改它.这似乎不必要地繁琐,并且必须有很多人分享我的痛苦,所以有没有办法在VS中的文件之间自动执行这些更改？

vim解决方案的奖励积分也是如此.