| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 5932 | Accepted: 2463 |
Frank N. Stein is a very conservative high-school teacher. He wants to take some of his students on an excursion, but he is afraid that some of them might become couples. While you can never exclude this possibility, he has made some rules that he thinks indicates a low probability two persons will become a couple:
So, for any two persons that he brings on the excursion, they must satisfy at least one of the requirements above. Help him find the maximum number of persons he can take, given their vital information.
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
3 7
Source
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 6 using namespace std; 7 8 const int N(500+15); 9 int t,n,h,ans; 10 11 int sumb,sumg; 12 struct Node 13 { 14 int heigh; 15 char music[119],sport[119]; 16 }boy[N],girl[N]; 17 18 int head[N],sumedge; 19 struct Edge 20 { 21 int u,v,next; 22 Edge(int u=0,int v=0,int next=0): 23 u(u),v(v),next(next){} 24 }edge[N*N]; 25 void ins(int u,int v) 26 { 27 edge[++sumedge]=Edge(u,v,head[u]); 28 head[u]=sumedge; 29 } 30 31 int vis[N],match[N]; 32 bool DFS(int x) 33 { 34 for(int i=head[x];i;i=edge[i].next) 35 { 36 int v=edge[i].v; 37 if(vis[v]) continue; 38 vis[v]=1; 39 if(!match[v]||DFS(match[v])) 40 { 41 match[v]=x; 42 return true; 43 } 44 } 45 return false; 46 } 47 48 void init() 49 { 50 ans=sumedge=sumb=sumg=0; 51 memset(boy,0,sizeof(boy)); 52 memset(girl,0,sizeof(girl)); 53 memset(head,0,sizeof(head)); 54 memset(match,0,sizeof(match)); 55 scanf("%d",&n); 56 } 57 58 int main() 59 { 60 scanf("%d",&t); 61 for(;t--;) 62 { 63 init();char xb; 64 for(int h,i=1;i<=n;i++) 65 { 66 scanf("%d",&h);cin>>xb; 67 if(xb==‘F‘) boy[++sumb].heigh=h,scanf("%s%s",boy[sumb].music,boy[sumb].sport); 68 else girl[++sumg].heigh=h,scanf("%s%s",girl[sumg].music,girl[sumg].sport); 69 } 70 for(int i=1;i<=sumb;i++) 71 for(int j=1;j<=sumg;j++) 72 if(abs(boy[i].heigh-girl[j].heigh)<=40&&!strcmp(boy[i].music,girl[j].music)&&strcmp(boy[i].sport,girl[j].sport)) 73 ins(i,j); 74 for(int i=1;i<=sumb;i++) 75 { 76 memset(vis,0,sizeof(vis)); 77 if(DFS(i)) ans++; 78 } 79 printf("%d\n",n-ans); 80 } 81 return 0; 82 }
POJ——T2271 Guardian of Decency
原文：http://www.cnblogs.com/Shy-key/p/7113177.html