题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1150
二分匹配题，题目求最小重启次数，即最小点覆盖，x集合为所有A机器模式，y集合为所有B机器模式，任务为边，求最小点覆盖，即图最大二分匹配，匈牙利算法
代码：
C语言: 高亮代码由发芽网提供
#include<stdio.h>
#include<string.h>
int map [ 100 ][ 100 ], m ,n;
int match [ 100 ], visit [ 100 ];
int DFS( int u)
{
int
i;
for(
i
=
1;
i
<=
m;
i
++)
{
if(
map
[
u
][
i
]
&&
visit
[
i
]
==-
1)
{
visit
[
i
]
=
1;
if(
match
[
i
]
==-
1 ||
DFS(
match
[
i
]))
{
match
[
i
]
=
u;
return
1;
}
}
}
return
0;
}
int main()
{
int
i
,
num
,
a
,b
,
c;
while(
scanf(
"%d"
,
&n
),n)
{
memset(
map
,
0
,
sizeof(
map));
scanf(
"%d%d"
,
&
m
,
&
num);
for(
i
=
0;
i
<
num;
i
++)
{
scanf(
"%d%d%d"
,
&
a
,
&b
,
&
c);
map
[b
][
c
]
=
1;
}
memset(
match
,
-
1
,
sizeof(
match));
num
=
0;
for(
i
=
1;
i
<=n;
i
++)
{
memset(
visit
,
-
1
,
sizeof(
visit));
if(
DFS(
i))
num
++;
}
printf(
"%d
\n
"
,
num);
}
return
0;
}
#include<string.h>
int map [ 100 ][ 100 ], m ,n;
int match [ 100 ], visit [ 100 ];
int DFS( int u)
{
}
int main()
{
}