本文主要是介绍HDUnbsp;1150nbsp;Machinenbsp;Schedule（二分…，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：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()
{
}
这篇关于HDUnbsp;1150nbsp;Machinenbsp;Schedule（二分…的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
