Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Re:同问，能够证明其正确性的acmer请解答下

Posted by 200730690105 at 2010-03-10 10:19:40 on Problem 1466
In Reply To:同问，能够证明其正确性的acmer请解答下 Posted by:lct_3 at 2010-03-09 19:47:17

最大独立数=未匹配的节点+匹配数/2   （1）
(设n=匹配数/2，可以理解为去掉二分图某侧匹配好的n个节点，在另一侧对应的n个节点就没有相匹配的了）
而 未匹配的节点=顶点数-匹配数      （2）
由（1）（2）得: 最大独立数=顶点数-匹配数的一半

Followed by:

Post your reply here: