Girls and Boys
Time Limit: 20000/10000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5565????Accepted Submission(s): 2481
?
Problem Description
the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.
?
The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description:
?
the number of students
the description of each student, in the following format
student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ...
or
student_identifier:(0)
?
The student_identifier is an integer number between 0 and n-1, for n subjects.
For each given data set, the program should write to standard output a line containing the result.
?
?
Sample Input
7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0
?
?
Sample Output
5
2
?
?
Source
Southeastern Europe 2000
?
?
Recommend
JGShining
嗯,看起來是個求最大獨(dú)立集的題,而且還是個二分圖.因?yàn)轭}里沒說有 Homosexuality,所以不會有奇環(huán).不過圖是用一般形式給出的算出來的匹配要除以2.
?
#include<stdio.h>
#include
<
string
.h>
int
n,m,match[
1024
];
bool
visit[
1024
],G[
1024
][
1024
];
bool
DFS(
int
k)
{
int
t;
for
(
int
i=
0
;i<m;i++
)
if
(G[k][i] && !
visit[i])
{
visit[i]
=
1
;
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=
0
;i<n;i++
)
{
memset(visit,
0
,
sizeof
(visit));
if
(DFS(i)) ans++
;
}
return
ans;
}
int
main()
{
int
t,a,b,c;
while
(scanf(
"
%d
"
,&t)!=
EOF)
{
n
=m=
t;
memset(G,
0
,
sizeof
(G));
while
(t--
)
{
scanf(
"
%d: (%d)
"
,&a,&
b);
for
(
int
i=
0
;i<b;i++
)
{
scanf(
"
%d
"
,&
c);
G[a][c]
=
1
;
}
}
printf(
"
%d\n
"
,n-Max_match()/
2
);
}
}
?
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
