POJ 2771 简单二分图匹配

题意：

给出样例个数T

给出一个n表示有n个人..

给出n个人的信息身高性别音乐风格喜欢的运动

如果身高差距超过40 性别一样音乐风格不一样喜欢的运动一样..

符合任何一项都不可以当夫妻..

然后问可以找出多少人不管怎么匹配都无法成为夫妻..

思路：

把男生女生分成两个集合..

然后根据是否符合变成夫妻的条件连线..

找出可以变成夫妻的最多对数..

然后用总数 - 就知道能够有多少人不管怎么样都无法成为夫妻..

Tips：

※ 遍历一个集合的时候记得for 循环的时候为了保证是从一个集合开始找增光路..所以要加一个if 语句来保证是一个集合的..

※ #define fabs(x) ((x)>0?(x):-(x)) 或写成函数形式..

这个原因wa了2次..o(╯□╰)o~

Code:

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 using namespace std;
 5 #define clr(x) memset(x, 0, sizeof(x))
 6 
 7 struct Person
 8 {
 9     int h;
10     char gen;
11     char mu[110];
12     char sp[110];
13 }p[510];
14 
15 struct Edge
16 {
17     int to;
18     int next;
19 }edge[1000000];
20 int head[510];
21 int tot;
22 
23 int fabs(int x)
24 {
25     if(x > 0) return x;
26     else return -x;
27 }
28 
29 void add(int s, int u)
30 {
31     edge[tot].to = u;
32     edge[tot].next = head[s];
33     head[s] = tot++;
34 }
35 
36 int link[510];
37 int vis[510];
38 int m, n;
39 
40 int dfs(int x)
41 {
42     for(int i = head[x]; i != 0; i = edge[i].next){
43         int y = edge[i].to;
44         if(!vis[y]){
45             vis[y] = true;
46             if(link[y] == 0 || dfs(link[y])){
47                 link[y] = x;
48                 return true;
49             }
50         }
51     }
52     return false;
53 }
54 
55 void solve()
56 {
57     for(int i = 1; i <= n; ++i){
58         clr(vis);
59         if(p[i].gen == 'M' && dfs(i))
60             m++;
61     }
62 }
63 
64 bool check(Person a, Person b)
65 {
66     if(fabs(a.h-b.h) <= 40 && strcmp(a.mu, b.mu) == 0 && strcmp(a.sp, b.sp) != 0)
67         return true;
68     else return false;
69 }
70 
71 int main()
72 {
73     int i, j, k;
74     int T;
75     while(scanf("%d", &T) != EOF)
76     while(T--)
77     {
78         tot = 1, m = 0;
79         clr(head), clr(link), clr(edge);
80 
81         scanf("%d", &n);
82         for(i = 1; i <= n; ++i){
83             scanf("%d %c %s %s", &p[i].h, &p[i].gen, p[i].mu, p[i].sp);
84      //       printf("%c\n", p[i].gen);
85         }
86 
87         for(i = 1; i <= n; ++i)
88         for(j = 1; j <= n; ++j)
89         if(i != j && p[i].gen == 'M' && p[j].gen == 'F' && check(p[i], p[j]))
90             add(i, j);
91 
92         solve();
93 
94         printf("%d\n", n-m);
95     }
96     return 0;
97 }