poj2771Guardian of Decency 二分匹配之最大独立集

时间：2015-08-05 20:29:15 阅读：377 评论：0 收藏：0 [点我收藏+]

//男生和女生需要一些条件就不是情侣
//问最多能带多少人，这些人中没有情侣
//很明显的最大独立集
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<string>
#include<cmath>
using namespace std ;
const int maxn = 510 ;
int vis[maxn] ;
int match[maxn] ; int n ;
vector<int> vec[maxn] ;
struct node
{
int h ;
string sex , m , f ;
}p[maxn] ;
bool find(int u)
{
for(int i = 0 ;i < vec[u].size() ;i++)
{
int v = vec[u][i] ;
if(!vis[v] && p[v].sex == "M")
{
vis[v] = 1 ;
if(match[v] == -1 || find(match[v]))
{
match[v] = u ;
return true ;
}
}
}
return false ;
}
bool judge(node a , node b)
{
if(abs((double)(a.h-b.h)) > 40 || a.sex == b.sex || a.m != b.m || a.f == b.f)
return false;
return true ;
}
int main()
{
int T ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%d" , &n) ;
for(int i = 1;i <= n;i++)
vec[i].clear() ;
memset(match , -1 , sizeof(match)) ;
for(int i = 1;i <= n;i++)
{
cin>>p[i].h>>p[i].sex>>p[i].m>>p[i].f ;
for(int j = 1;j < i ; j++)
if(judge(p[i] , p[j])){
vec[i].push_back(j) ;
vec[j].push_back(i) ;
}
}
int ans = 0 ;
for(int i = 1;i <= n;i++)
{
memset(vis , 0 , sizeof(vis)) ;
if(p[i].sex == "F" && find(i))
ans++ ;
}
cout<<n - ans<<endl;
}
}

原文：http://blog.csdn.net/cq_pf/article/details/47301709

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)