本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分图 + 强连通分量
题意:略,和poj 1904差不多
- 对图求一次二分匹配,得到最大匹配数为res
- 因为男女人数不一定相同,题目也没有保证一定有完备匹配,所以当最大匹配为res的时候,男方有n-res个点没有匹配,女方有m-res个点没有匹配。
- 对于每一个没有匹配的男方,都虚构一个女子出来,直接跟他匹配,那么一共虚构出n-res个女子;对于每一个没有匹配的女方,都虚构出一个男子,直接跟她匹配,那么一共虚构出m-res个女子。可知,虚构完成后,男女方的人数都输,n+m-res。这样做就得到了一个完备匹配
- 此时,男女方点数都是n+m-res。对于每个虚构的男子,它喜欢所有n+m-res个女子,连n+m-res条边;对于每个虚构的女子,它被所有n+m-res个男子喜欢,被连n+m-res条边;这样整个图就构造完成
- 对于这个图,就回到了poj 1904的做法,对于每个男子,找到和它匹配的女子,为wife,然后看看这个男子还喜欢什么女子v,wife —> v,这样就构好了有向图,在这个有向图上求一次SCC
- 然后看看wife处在哪个连通分量,如果喜欢的v也在这个连通分量,则加进来。注意,虚构的v就没必要加了
1 |
|