Cat VS Dog
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 2046 Accepted Submission(s): 719
Problem Description
The zoo have N cats and M dogs, today there are P children visiting the zoo, each child has a like-animal and a dislike-animal, if the child's like-animal is a cat, then his/hers dislike-animal must be a dog, and vice versa.
Now the zoo administrator is removing some animals, if one child's like-animal is not removed and his/hers dislike-animal is removed, he/she will be happy. So the administrator wants to know which animals he should remove to make maximum number of happy children.
Input
The input file contains multiple test cases, for each case, the first line contains three integers N <= 100, M <= 100 and P <= 500.
Next P lines, each line contains a child's like-animal and dislike-animal, C for cat and D for dog. (See sample for details)
Output
For each case, output a single integer: the maximum number of happy children.
Sample Input
1 1 2
C1 D1
D1 C1
1 2 4
C1 D1
C1 D1
C1 D2
D2 C1
Sample Output
1
3
Hint
Case 2: Remove D1 and D2, that makes child 1, 2, 3 happy.
Source
2011 Multi-University Training Contest 1 - Host by HNU
Recommend
xubiao
分析:如果两个小朋友满足以下情况:1.A喜欢的是B讨厌的.2.A讨厌的是B喜欢的.此时这两个小朋友肯定不能同时高兴,那么就在他们之间连一条边.只要求出此图的最大独立集即可.
#include<stdio.h>
#include
<
string
.h>
int
N,M,P;
int
match[
600
];
bool
visit[
600
],G[
600
][
600
];
char
sl[
600
],sd[
600
];
int
pl[
600
],pd[
600
];
bool
DFS(
int
k)
{
for
(
int
i=
1
;i<=P;i++
)
if
(G[k][i] && !
visit[i])
{
visit[i]
=
1
;
int
t=
match[i];
match[i]
=
k;
if
(t==-
1
|| DFS(t))
return
true
;
match[i]
=
t;
}
return
false
;
}
int
Max_match()
{
int
ans=
0
;
memset(match,
-
1
,
sizeof
(match));
for
(
int
i=
1
;i<=P;i++
)
{
memset(visit,
0
,
sizeof
(visit));
if
(DFS(i)) ans++
;
}
return
ans;
}
int
main()
{
char
tmp;
int
i,j;
while
(scanf(
"
%d%d%d
"
,&N,&M,&P)!=
EOF)
{
tmp
=
getchar();
for
(i=
1
;i<=P;i++
)
{
scanf(
"
%c%d %c%d
"
,&sl[i],&pl[i],&sd[i],&
pd[i]);
tmp
=
getchar();
}
memset(G,
0
,
sizeof
(G));
for
(i=
1
;i<=P;i++
)
for
(j=
1
;j<=P;j++
)
if
(i!=
j)
{
if
(pl[i]==pd[j] && sl[i]==sd[j]) G[i][j]=
1
;
if
(pd[i]==pl[j] && sd[i]==sl[j]) G[i][j]=
1
;
}
printf(
"
%d\n
"
,P-Max_match()/
2
);
}
return
0
;
}
