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
;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
