最大独立数 poj 2771 Guardian of Decency

【最大独立数poj 2771 Guardian of Decency】题意:人与人之间满足4个条件之一即不能成为一对(也就说这4个条件都不满足才能成为一对) , 求可能的最多的单身人数 。
思路:把男女分为两部分,接下来就是二分图的匹配问题 。把能成为一对的之间连边 , 然后求出最大匹配 。题目要求的是最大独立数 。

最大独立数  poj 2771 Guardian of Decency

文章插图
最大独立数=顶点数-最大匹配数
#include#include#include#includeusing namespace std;#define MAXN 1024struct person{int h;char music[105];char sport[105];}male[MAXN],female[MAXN];int n,m,k,x,y,pre[MAXN];//二分图中X集和Y集的节点数各为n、m,边数为k;匹配边集为pre , 其中节点i所在的匹配边为(pre[i],i)bool v[MAXN],a[MAXN][MAXN];//设二分图相邻矩阵为a,Y集合中节点的访问标志为v , 若Y集合中的节点j已访问 , 则v[j]=truebool dfs(int i){//判断以X集合中的节点i为起点的增广路径是否存在int j;for(j=0; j View Code