hdu 1068 Girls and Boys
15453 ワード
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2013 Accepted Submission(s): 876
これは私が初めて二分図の問題を書いたので、最初は問題を読む時少しぼんやりしていましたが、それから大牛の指摘を得て、また二分図に関する本を読んで、やっと二分図について少し理解しました.
実は本題は主に最大の孤立点セットを求めます:最大の独立セット=点-最大のマッチング数;
ただし、ボリュームは、ポイントセットを(A)(B)に分割するのではなく、ポイントセット全体から検索されるため、最大マッチング数を求める場合は最大マッチング数/2を求めるべきであることに注意すべきである.
実行コード:
これは私が初めて二分図の問題を書いたので、最初は問題を読む時少しぼんやりしていましたが、それから大牛の指摘を得て、また二分図に関する本を読んで、やっと二分図について少し理解しました.
実は本題は主に最大の孤立点セットを求めます:最大の独立セット=点-最大のマッチング数;
ただし、ボリュームは、ポイントセットを(A)(B)に分割するのではなく、ポイントセット全体から検索されるため、最大マッチング数を求める場合は最大マッチング数/2を求めるべきであることに注意すべきである.
実行コード:
1
#include
<
stdio.h
>
2
#include
<
string
.h
>
3
int
n;
4
int
g[
1000
][
1000
];
5
int
mark[
1000
],ym[
1000
];
6
int
chk[
1000
];
7
int
searchpath(
int
u)
8
{
9
int
v;
10
for
(v
=
0
;v
<
n;v
++
)
11
if
(g[u][v]
==
1
&&
!
chk[v])
12
{
13
chk[v]
=
1
;
14
if
(ym[v]
==-
1
||
searchpath(ym[v]))
15
{
16
ym[v]
=
u;mark[u]
=
1
;
17
return
1
;
18
}
19
}
20
return
0
;
21
}
22
int
maxmatch()
23
{
24
int
u,ret
=
0
;
25
memset(mark,
0
,
sizeof
(mark));
26
memset(ym,
-
1
,
sizeof
(ym));
27
for
(u
=
0
;u
<
n;u
++
)
28
if
(mark[u]
==
0
)
29
{
30
memset(chk,
0
,
sizeof
(chk));
31
if
(searchpath(u))
32
ret
++
;
33
}
34
return
ret;
35
}
36
int
main()
37
{
38
int
i,j,s,c,a,b;
39
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
40
{
41
memset(g,
0
,
sizeof
(g));
42
for
(j
=
0
;j
<
n;j
++
)
43
{
44
scanf(
"
%d: (%d)
"
,
&
a,
&
b);
45
for
(i
=
1
;i
<=
b;i
++
)
46
{
47
scanf(
"
%d
"
,
&
c);
48
g[a][c]
=
1
;
49
}
50
}
51
printf(
"
%d
"
,n
-
maxmatch()
/
2
);
52
}
53
return
0
;
54
}
55