| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 5916 | Accepted: 2458 |
Description
Input
Output
Sample Input
2
4
35 M classicism programming
0 M baroque skiing
43 M baroque chess
30 F baroque soccer
8
27 M romance programming
194 F baroque programming
67 M baroque ping-pong
51 M classicism programming
80 M classicism Paintball
35 M baroque ping-pong
39 F romance ping-pong
110 M romance Paintball
Sample Output
3
7
Source
题意:现在有一个老师想带领他的学生出去郊游,但是他非常担心在郊游的过程中有些学生会发生恋爱关系,而他认为发生恋爱关系的可能性比较小的判断标准有以下四个,如果满足四个条件中的任何一个,即被他认为可能发生恋爱关系的可能性比较小:
1>两人身高的差距超过40cm;现在给出n个学生,并给出每个学生的信息(信息为:身高 性别 所喜欢的音乐风格 喜爱的运动),要求求解最大可以带出去郊游的学生数.
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 510 using namespace std; char ch; bool vis[N]; int t,n,x,ans,gnum,bnum,pre[N],map[N][N]; struct nn { int h; char fm[10000]; char fs[10000]; }girl[N],boy[N]; int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1; ch=getchar();} while(ch<=‘9‘&&ch>=‘0‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } void add_edge() { for(int i=1;i<=bnum;i++) for(int j=1;j<=gnum;j++) if(!strcmp(boy[i].fm,girl[j].fm)&&strcmp(boy[i].fs,girl[j].fs)&&abs(boy[i].h-girl[j].h)<=40) map[i][j]=1; } int find(int x) { for(int i=1;i<=gnum;i++) if(!vis[i]&&map[x][i]) { vis[i]=true; if(pre[i]==0||find(pre[i])) { pre[i]=x; return 1; } } return 0; } int main() { t=read(); while(t--) { ans=0;bnum=0,gnum=0; memset(boy,0,sizeof(boy)); memset(girl,0,sizeof(girl)); memset(pre,0,sizeof(pre)); memset(map,0,sizeof(map)); n=read(); for(int i=1;i<=n;i++) { x=read(); scanf("%c",&ch); if(ch==‘F‘) { girl[++gnum].h=x; cin>>girl[gnum].fm; cin>>girl[gnum].fs; } else { boy[++bnum].h=x; cin>>boy[bnum].fm; cin>>boy[bnum].fs; } } add_edge(); for(int i=1;i<=bnum;i++) { memset(vis,0,sizeof(vis)); if(find(i)) ans++; } printf("%d\n",n-ans); } return 0; }
原文：http://www.cnblogs.com/z360/p/7107170.html