题目链接:https://vjudge.net/problem/UVALive-3415
题解:
题意:选出尽可能多的人, 使得他(她)们之间不会擦出火花。即求出最大独立集。
1.因为性别有男女之分,所以此题的模型是个天然的二分图。
2.如果两个人之间可能擦出火花(即4条限定都不满足),则在他和她之间连一条边。
3.用匈牙利算法求出最小覆盖点数(即最大匹配数),然后最大独立集的元素个数就是总结点数减去最小覆盖点数。
4.为何:最大独立集 = 总体 - 最小覆盖点集 ?
答:最大独立集也可以这么理解:在二分图中, 删去尽可能少的点, 使得剩下的点互相独立,即没有边的存在。而我们又知道,最小覆盖点集覆盖掉了所有的边,当我们把这些点都删去了,就不存在边了。而又因为是“最小”覆盖点集,即删除了最少的点,而得到了最大独立集。
代码如下:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <string> 6 #include <vector> 7 #include <map> 8 #include <set> 9 #include <queue> 10 #include <sstream> 11 #include <algorithm> 12 using namespace std; 13 const int INF = 2e9; 14 const int MOD = 1e9+7; 15 const int MAXN = 1e3+10; 16 17 int n; 18 int M[MAXN][MAXN], link[MAXN]; 19 bool vis[MAXN]; 20 21 struct Node 22 { 23 int h; 24 string sex, music, sport; 25 }student[MAXN]; 26 27 bool dfs(int u) 28 { 29 for(int i = 1; i<=n; i++) 30 if(M[u][i] && !vis[i]) 31 { 32 vis[i] = true; 33 if(link[i]==-1 || dfs(link[i])) 34 { 35 link[i] = u; 36 return true; 37 } 38 } 39 return false; 40 } 41 42 int hungary() 43 { 44 int ret = 0; 45 memset(link, -1, sizeof(link)); 46 for(int i = 1; i<=n; i++) 47 { 48 memset(vis, 0, sizeof(vis)); 49 if(dfs(i)) ret++; 50 } 51 return ret; 52 } 53 54 bool judge(Node x, Node y) 55 { 56 return (abs(x.h-y.h)<=40 && x.sex!=y.sex 57 && x.music==y.music && x.sport!=y.sport); 58 } 59 60 int main() 61 { 62 int T; 63 scanf("%d", &T); 64 while(T--) 65 { 66 scanf("%d", &n); 67 for(int i = 1; i<=n; i++) 68 cin>>student[i].h>>student[i].sex>>student[i].music>>student[i].sport; 69 70 memset(M, 0, sizeof(M)); 71 for(int i = 1; i<=n; i++) 72 for(int j = 1; j<=n; j++) 73 if(i!=j && judge(student[i], student[j])) 74 M[i][j] = 1; 75 76 int cnt = hungary()/2; 77 printf("%d\n", n-cnt); 78 } 79 }