有一个集合男和一个集合女,给出两集合间一些一一对应关系,问该两集合中的最大独立集的点数。
最大独立集=顶点总数-最大匹配数
此题中,若(a,b)有关,则(b,a)有关,每一个关系算了两次,相当于二分图的两边集合没有分男女,两边都是总人数,
所以此题中答案应该是 顶点总数-最大匹配数/2
#include
#include
#include
#include
#include
#include
#include
const int maxn=510; using namespace std; int mx[maxn],my[maxn],vis[maxn],e[maxn][maxn],n; int path(int i) { int j; for(j=0;j