题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1059

YY一下可以发现，假如某个黑色格子用掉了，那么与其同行同列的所有格子都不能用了，而且与其他行列的格子无关，那么就二分图匹配啦~

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define MAXN 100010

#define AddEdge( s , t , f ) Add( s , t , f ) , Add( t , s , 0 )

#define inf 0x7fffffff

 

struct edge {

    int next , t , f ;

} E[ MAXN ] ;

 

int head[ MAXN ] , Index ;

 

void Add( int s , int t , int f ) {

    E[ Index ].t = t , E[ Index ].f = f , E[ Index ].next = head[ s ] ;

    head[ s ] = Index ++ ;

}

 

int node[ MAXN ][ 2 ] , V , S , T ;

int gap[ MAXN ] , h[ MAXN ] , d[ MAXN ] ;

 

int sap( int v , int flow ) {

    if ( v == T ) return flow ;

    int rec = 0 ;

    for ( int p = d[ v ] ; p != - 1 ; p = E[ p ].next ) {

        if ( E[ p ].f && h[ v ] == h[ E[ p ].t ] + 1 ) {

            int ret = sap( E[ p ].t , min( flow - rec , E[ p ].f ) ) ;

            E[ p ].f -= ret , E[ p ^ 1 ].f += ret , d[ v ] = p ;

            if ( ( rec += ret ) == flow ) return flow ;

        }

    }

    if ( ! ( -- gap[ h[ v ] ] ) ) h[ S ] = T ;

    gap[ ++ h[ v ] ] ++ , d[ v ] = head[ v ] ;

    return rec ;

}

 

int maxflow(  ) {

    memset( gap , 0 , sizeof( gap ) ) ;

    memset( h , 0 , sizeof( h ) ) ;

    for ( int i = 0 ; i ++ < T ; ) d[ i ] = head[ i ] ;

    gap[ 0 ] = T ;

    int flow = 0 ;

    while ( h[ S ] < T ) flow += sap( S , inf ) ;

    return flow ;

}

 

int tot , n ;

 

int main(  ) {

    scanf( "%d" , &tot ) ;

    while ( tot -- ) {

        Index = V = 0 ;

        scanf( "%d" , &n ) ;

        for ( int i = 0 ; i ++ < n ; ) {

            node[ i ][ 0 ] = ++ V , node[ i ][ 1 ] = ++ V ;

        }

        S = ++ V ; T = ++ V ;

        for ( int i = 0 ; i ++ < V ; ) head[ i ] = - 1 ;

        for ( int i = 0 ; i ++ < n ; ) {

            AddEdge( S , node[ i ][ 0 ] , 1 ) , AddEdge( node[ i ][ 1 ] , T , 1 ) ;

            for ( int j = 0 ; j ++ < n ; ) {

                int x ; scanf( "%d" , &x ) ;

                if ( x ) AddEdge( node[ i ][ 0 ] , node[ j ][ 1 ] , 1 ) ;

            }

        }

        printf( maxflow(  ) == n ? "Yes\n" : "No\n" ) ;

    }

    return 0 ;

}