hdu 2768(最大独立集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2768

思路：把喜欢cat的和喜欢dog的看成两个集合，如果这两个集合有冲突，即cat.love==dog.hate或者cat.hate==dog.love，这连边，代表有矛盾，那么最后的结果不就是求一下最大独立集吗。

最大独立集=顶点数-最大匹配。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 #define MAXN 2222
 8 struct Node {
 9     string love;
10     string hate;
11 } cat[MAXN],dog[MAXN];
12 int cat_cnt,dog_cnt;
13 bool map[MAXN][MAXN];
14 bool mark[MAXN];
15 int ly[MAXN];
16 char s1[11],s2[11];
17 
18 int dfs(int u) {
19     for(int v=0; v<dog_cnt; v++) {
20         if(map[u][v]&&!mark[v]) {
21             mark[v]=true;
22             if(ly[v]==-1||dfs(ly[v])) {
23                 ly[v]=u;
24                 return 1;
25             }
26         }
27     }
28     return 0;
29 }
30 
31 int MaxMatch() {
32     int res=0;
33     memset(ly,-1,sizeof(ly));
34     for(int i=0; i<cat_cnt; i++) {
35         memset(mark,false,sizeof(mark));
36         res+=dfs(i);
37     }
38     return res;
39 }
40 
41 int main() {
42 //   freopen("1.txt","r",stdin);
43     int _case,c,d,v;
44     scanf("%d",&_case);
45     while(_case--) {
46         scanf("%d%d%d",&c,&d,&v);
47         cat_cnt=dog_cnt=0;
48         for(int i=0; i<v; i++) {
49             scanf("%s%s",s1,s2);
50             if(s1[0]=='C') {
51                 cat[cat_cnt].love=s1;
52                 cat[cat_cnt++].hate=s2;
53             } else {
54                 dog[dog_cnt].love=s1;
55                 dog[dog_cnt++].hate=s2;
56             }
57         }
58         memset(map,false,sizeof(map));
59         for(int i=0; i<cat_cnt; i++) {
60             for(int j=0; j<dog_cnt; j++) {
61                 if(cat[i].love==dog[j].hate||cat[i].hate==dog[j].love) {
62                     map[i][j]=true;
63                 }
64             }
65         }
66         int ans=MaxMatch();
67         printf("%d\n",v-ans);
68     }
69     return 0;
70 }

View Code