UVALive3415 Guardian of Decency —

UVALive3415 Guardian of Decency —— 最大独立集

题目链接：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-cnt);
78     }
79 }

View Code