题意:人与人之间满足4个条件之一即不能成为一对(也就说这4个条件都不满足才能成为一对),求可能的最多的单身人数。

思路:把男女分为两部分,接下来就是二分图的匹配问题。把能成为一对的之间连边,然后求出最大匹配。题目要求的是最大独立数。

最大独立数=顶点数-最大匹配数

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; #define MAXN 1024 struct person{
int h;
char music[];
char sport[];
}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]=true bool dfs(int i){//判断以X集合中的节点i为起点的增广路径是否存在
int j;
for(j=; j<m; j++){
if(!v[j]&&a[i][j]){//搜索所有与i相邻的未访问点
v[j]=;//访问节点j
if(pre[j]==-||dfs(pre[j])){
//若j的前驱是未盖点或者存在由j的前驱出发的增广路径,则设定(i,j)为匹配边,返回成功标志
pre[j]=i;
return true;
}
}
}
return false;//返回失败标志
} int main(){
int t,num,h;
char sex[];
int i,j,ans;
scanf("%d",&t);
while(t--){
memset(a,,sizeof(a));//二分图的相邻矩阵初始化
memset(pre,-,sizeof(pre));//匹配边集初始化为空
n=m=;
scanf("%d",&num);
while(num--){
scanf("%d%s",&h,sex);
if(sex[]=='M'){
male[n].h=h;
scanf("%s%s",male[n].music,male[n].sport);
++n;
}
else{
female[m].h=h;
scanf("%s%s",female[m].music,female[m].sport);
++m;
}
}
for(i=;i<n;++i){
for(j=;j<m;++j){
if(abs(male[i].h-female[j].h)<=&&strcmp(male[i].music,female[j].music)==&&strcmp(male[i].sport,female[j].sport)!=)
a[i][j]=;
}
}
ans=;//匹配边数初始化为0
for(i=; i<n; i++){//枚举X集的每个节点
memset(v,,sizeof(v));//设Y集合中的所有节点的未访问标志
if(dfs(i)) ans++;//若节点i被匹配边覆盖,则匹配边数+1
}
printf("%d\n",n+m-ans);
}
return ;
}

最新文章

  1. jquery each函数 break和continue功能
  2. iOS 添加中文支持的操作
  3. Spring中Bean的作用域
  4. 【python】题目:有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?
  5. linux kernel 如何处理大小端
  6. iOS学习之内存管理
  7. 读取 RSSI
  8. Solaris桌面CDE
  9. 互联网科技今年九个兴奋点:O2O深耕细作,可穿戴设备分水岭
  10. Tomcat源码分析--转
  11. ETL控件学习之一从数据库导出数据到平面
  12. Node.js中的exports与module.exports的区分
  13. &lt;Win32_12&gt;程序员求爱的创意程序——升级版^_^
  14. 浏览器兼容之Chrome浏览器: -webkit-text-size-adjust: none;
  15. 分享 android 源码
  16. C语言学习之弹跳小球
  17. ACM Ignatius and the Princess I
  18. WP8.1开发:简单天气预报应用(转)
  19. linux中守护进程启停工具start-stop-daemon
  20. 细说Unity3D(一)——移动平台动态读取外部文件全解析

热门文章

  1. python常用模块详解(一)
  2. T2832 6个朋友 codevs
  3. haproxy和nginx负载均衡分析
  4. jquery 获取浏览器窗口的可视区域高度 宽度 滚动条高
  5. ios实现下载图片的裁减和显示
  6. 校园网、教育网 如何纯粹访问 IPv6 网站避免收费
  7. 完整的MVC框架(前端、后台和数据库)
  8. 国内90%以上的 iOS 开发者,对 APNs 的认识都是错的
  9. 生活娱乐 360安全卫士和QQ大战
  10. mac系统下为emacs设置中文字体,解决乱码问题