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