Posted on 2008-08-01 19:39
Hero 阅读(175)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
/* Accepted 1140 C++ 00:01.10 500K */
//还是二部图
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
const int INF = 1000000 ;
const int size = 310 ;
int testnum, ct ;
int inp, inn ;
bool link[size][size] ;
int Binmatch( int inn, int inm )
{
int matchnum = 0 ; int dn_node ;
int queue[size*10] ; int head=0, tail = 0 ;//定义队列
int upmatch[size], dnmatch[size] ; int prev[size] ;
memset( upmatch, -1, sizeof(upmatch) ) ;
memset( dnmatch, -1, sizeof(dnmatch) ) ;
for( int i=1; i<=inn; i++ ) {
for( int j=1; j<=inm; j++ ) prev[j] = -2 ;
head = tail = 0 ;
for( int j=1; j<=inm; j++ ) if( link[i][j] )
{ prev[j] = -1 ; queue[tail++] = j ; }
while( head < tail ) {
dn_node = queue[head] ;
if( -1 == dnmatch[dn_node] ) break ;
head++ ;
for( int j=1; j<=inm; j++ ) if( -2==prev[j]&&link[dnmatch[dn_node]][j] )
{ prev[j] = dn_node ; queue[tail++] = j ; }
}
if( head == tail ) continue ;
while( prev[dn_node] > -1 ) {
upmatch[dnmatch[prev[dn_node]]] = dn_node ;
dnmatch[dn_node] = dnmatch[prev[dn_node]] ;
dn_node = prev[dn_node] ;
}
dnmatch[dn_node] = i ; upmatch[i] = dn_node ;
matchnum++ ;
}
return matchnum ;
}
int main()
{
//freopen( "frac1.in", "r", stdin ) ;
//freopen( "frac1.out","w",stdout ) ;
int sn, en, numlink ;
while( scanf( "%d",&testnum ) != EOF )
{
for( ct=1; ct<=testnum; ct++ )
{
memset( link, false, sizeof(link) ) ;
scanf( "%d %d",&inp, &inn ) ;
for( int sn=1; sn<=inp; sn++ ) {
scanf( "%d",&numlink ) ;
while( numlink -- ) {
scanf( "%d",&en ) ; link[sn][en] = true ;
}
}//data input
int matchnum = Binmatch( inp, inn ) ;
if( matchnum == inp ) printf( "YES\n" ) ;
else printf( "NO\n" ) ;
}
}//while
return 0 ;
}