a1b3c7d9的博客

博客

求助,带权拟阵交

2019-11-27 21:11:31 By a1b3c7d9

这个是什么意思啊(出自2018集训队论文)

$$\max_{I\in I_1\cap I_2}\sum_{e\in I}w(e)=\min_{w_1,w_2:任意x,有w_1(x)+w_2(x)=w(w)}(\max_{I\in I_1}w_1(I)+\max_{I\in I_2}w_2(I))$$

a1b3c7d9

式子太长，有遮挡，见谅，建议去看论文

2019-11-27 21:12:27
回复

a1b3c7d9

顺便问一下,到底怎么求带权拟阵交？因为论文好像有误，给个权威点的解答

2019-11-28 19:02:27
回复

a1b3c7d9

拟阵交做二分图匹配，咋是$O(n^4)$,如何优化？

2019-11-28 21:14:00
回复

liu_cheng_ao

原式似乎打错了，应该是 $\omega_1(x)+\omega_2(x)=\omega(x)$ 而非 $\dots=\omega(w)$？这样左边 $= \max \sum_{e\in I} \omega_1(e)+\omega_2(e) \le \max_{I\in \mathcal I_1} \sum_{e\in I} \omega_1(e)+ \max_{I\in \mathcal I_2} \sum_{e\in I}\omega_2(e) \le $ 右边。

2019-11-29 16:51:02
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。