 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:关于有向图的最大匹配问题描述成二分图的最大匹配In Reply To:Re:关于有向图的最大匹配问题描述成二分图的最大匹配 Posted by:JNUZL at 2012-02-14 22:07:46 > 呃，做法是，把原图中的每个点拆做两个点i1和i2。如果原图中存在一条边a->b的话则在二分图中连接a1->b2。然后对构造出的二分图求最大匹配即可。因为最大匹配的特点就是，二分图中的每个点上最多只属于一条匹配边，所以拆出的两点就分别可以来限制这个点的入度和出度。 表达能力有限，还有问题的话可以加我的Q~~ Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
