hdu 2063-ジェットコースター
1319 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=2063
ハンガリーのアルゴリズムDFSの拡大入門問題
ハンガリーのアルゴリズムDFSの拡大入門問題
#include<stdio.h>
#include<cstring>
#define MAXN 1005
int nx , ny ;
int g[ MAXN ][ MAXN ] ;
int cx[ MAXN ], cy[ MAXN ] ;
int mk[ MAXN ] ;
int m , n ;
int path( int u )
{
for( int v = 0 ; v < n ; v++ )
{
if( g[ u ][ v ] && !mk[ v ] )
{
mk[ v ] = 1 ;
if( cy[ v ] == -1 || path( cy[ v ] ) )
{
cx[ u ] = v ;
cy[ v ] = u ;
return 1 ;
}
}
}
return 0 ;
}
int MaxMatch()
{
int res = 0 ;
memset( cx , 0xff , sizeof( cx ) ) ;
memset( cy , 0xff , sizeof( cy ) ) ;
for( int i = 0 ; i <= m ; i++ )
{
if( cx[ i ] == -1 )
{
memset( mk , 0 , sizeof( mk ) ) ;
res += path( i ) ;
}
}
return res ;
}
int main()
{
int i , j ;
int k ;
int x , y ;
while( scanf( "%d" ,&k )!= EOF && k )
{
scanf( "%d%d" , &m ,&n ) ;
memset( g , 0 , sizeof( g ) ) ;
for( i = 0 ; i < k ; i++ )
{
scanf( "%d%d" , &x, &y ) ;
g[ x - 1 ][ y - 1 ] = 1 ;
}
int sum =0 ;
printf( "%d
" , MaxMatch() ) ;
}
}