算法輪廓：
(1)置M為空
(2)找出一條增廣路徑P，通過取反操作獲得更大的匹配M’代替M
(3)重復(fù)(2)操作直到找不出增廣路徑為止
V2:
#include?
<
iostream
>
#include?
<
fstream
>
?
using
?
namespace
?std;
const
?
int
?MAXN?
=
?
100
;
int
?uN,?vN;??
//
u,ｖ數(shù)目?
bool
?g[MAXN][MAXN];
//
g[i][j]?表示?xi與yj相連?
int
?xM[MAXN],?yM[MAXN];?
//
?輸出量?
bool
?chk[MAXN];?
//
輔助量?檢查某輪?y[v]是否被check?
bool
?SearchPath(
int
?u)
{
????
int
?v;
????
for
?(v
=
0
;?v
<
vN;?v
++
)
????
{
????????
if
?(g[u][v]?
&&
?
!
chk[v])
????????
{
????????????chk[v]?
=
?
true
;
????????????
if
?(yM[v]?
==
?
-
1
?
||
?SearchPath(yM[v]))?
????????????
{
????????????????yM[v]?
=
?u;
????????????????xM[u]?
=
?v;
????????????????
return
?
true
;
????????????}
????????}
????}
????
return
?
false
;
}
int
?MaxMatch()
{
????
int
?u;
????
int
?ret?
=
?
0
;
????memset(xM,?
-
1
,?
sizeof
(xM));
????memset(yM,?
-
1
,?
sizeof
(yM));
????
for
?(u
=
0
;?u
<
uN;?u
++
)
????
{
????????
if
?(xM[u]?
==
?
-
1
)
????????
{
????????????memset(chk,?
false
,?
sizeof
(chk));
????????????
if
?(SearchPath(u))?ret
++
;
????????}
????}
????
return
?ret;
}
int
?main()
{
????
int
?i,?k;?
????
int
?tU,?tV;
????ifstream?cin(
"
test.txt
"
);
????cin?
>>
?uN?
>>
?vN?
>>
?k;
????memset(g,?
false
,?
sizeof
(g));
????
for
?(i
=
0
;?i
<
k;?i
++
)
????
{
????????cin?
>>
?tU?
>>
?tV;
????????g[tU][tV]?
=
?
true
;
????}
?
????
int
?M?
=
??MaxMatch();
????cout?
<<
?
"
Total?Match:?
"
?
<<
?M?
<<
?endl;
????
for
?(i
=
0
;?i
<
MAXN;?i
++
)
????????
if
?(xM[i]?
!=
?
-
1
)
????????????cout?
<<
?i?
<<
?
'
?
'
?
<<
?xM[i]?
<<
?endl;
????system(
"
pause
"
);
????
????
return
?
0
;?
}
?
/**/
/*
**********
test?data:
????3?3?3
????1?1
????1?0
????2?2
**********
*/
?
posted on 2006-10-01 02:15
豪 閱讀(4338)
評論(7) 編輯 收藏 引用 所屬分類:
數(shù)據(jù)結(jié)構(gòu)與算法