hdu 3829 Cat VS Dog

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分图 最大独立集

题意:有p个人,n个猫m个狗,每个人喜欢猫就一定讨厌狗,喜欢狗一定讨厌猫,选出最多的人,使得选出的人中,不会出现任意两个人发生矛盾,即一个人喜欢的动物是另一个人讨厌的。

以人作为点而不是猫狗,把喜欢猫的人作为X部,把喜欢狗的人作为Y部,X里面的人如果和Y里面的人发生了矛盾,那么就连一条边。X部或Y部内部是不会有边,例如X部,里面的人都是喜欢猫讨厌狗的。这样就得到了一个二分图模型,题意就是要我们求最大独立集,即选出最大的人它们之间都没有边。那就是求最大匹配用总人数减去即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 510
#define M 250010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,a,b,tot,head[N];
struct edge{
int v,next;
}e[M];
struct man{
char s1[10];
char s2[10];
}p[N],q[N];
int match[N];
bool vis[N];

inline bool check(int i,int j){
if(!strcmp(p[i].s2 , q[j].s1)) return true;
if(!strcmp(q[j].s2 , p[i].s1)) return true;
return false;
}

inline void add(int u,int v){
e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
}

int dfs(int u){
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!vis[v]){
vis[v] = true;
if(match[v] == -1 || dfs(match[v])){
match[v] = u; return 1;
}
}
}
return 0;
}

void MaxMatch(){
int ans = 0;
cl(match,-1);
for(int i = 1; i <= a; i++){
cl(vis,false);
ans += dfs(i);
}
printf("%d\n",n-ans);
}

int main(){
int t1,t2;
while(scanf("%d%d%d",&t1,&t2,&n)!=EOF){
a = b = 0;
for(int i = 1; i <= n; i++){
char s1[10],s2[10];
scanf("%s%s",s1,s2);
if(s1[0] == 'C'){
strcpy(p[++a].s1 , s1);
strcpy(p[a].s2 , s2);
}
else{
strcpy(q[++b].s1 , s1);
strcpy(q[b].s2 , s2);
}
}
tot = 0; cl(head,-1);
for(int i = 1; i <= a; i++)
for(int j = 1; j <= b; j++)
if(check(i,j))
add(i,j);
MaxMatch();
}
return 0;
}