[POJ 1904]强连通分量、二分图匹配、巧妙转化** 发布者:edward_mj 26 1 月, 2010 于[POJ 1904]强连通分量、二分图匹配、巧妙转化**留下评论 【题目大意】有N个女生,N个男生,给定一些边表示这两个人可以结婚。再给定一个初始匹配,表示这个男生和哪个女生结婚。初始匹配必定是合法的。然后让你求每个男生可以和哪几个女生结婚,使得所有人都能得到婚配。 【算法分析】如果男生A可以和女生B结婚,那么连边[A,B],如果初始匹配[A,B],那么连边[B,A],最后,如果在同一个强连通分量以内,则表示可以结婚。 其实就是二分图匹配中的寻找增广路的过程,可以自己体会。 【CODE】 #include