[POJ 1904]强连通分量、二分图匹配、巧妙转化**

【题目大意】有N个女生,N个男生,给定一些边表示这两个人可以结婚。再给定一个初始匹配,表示这个男生和哪个女生结婚。初始匹配必定是合法的。然后让你求每个男生可以和哪几个女生结婚,使得所有人都能得到婚配。

【算法分析】如果男生A可以和女生B结婚,那么连边[A,B],如果初始匹配[A,B],那么连边[B,A],最后,如果在同一个强连通分量以内,则表示可以结婚。

其实就是二分图匹配中的寻找增广路的过程,可以自己体会。

【CODE】

#include

留下评论

您的邮箱地址不会被公开。 必填项已用 * 标注