gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2226--Muddy Fields

二分图匹配，关键：建图

#include <stdio.h>
#include <memory.h>

const int max = 1001 ;

bool use[max] , map[max][max] ;
int link[max] ;
int LNum , RNum ;

const int MaxSize = 51 ;
char cTemp[MaxSize][MaxSize] ;

//建图
void Build(int r, int c)
{
    int i , j , k ;

    LNum = 0 ;
    RNum = 0 ;

    int LeftMem[MaxSize][MaxSize] ;

    memset( LeftMem, 0xff, sizeof(LeftMem) ) ;

    memset( map, 0, sizeof(map) ) ;
    memset( link, 0xff, sizeof(link) ) ;

    for ( i = 0 ; i < r ; i++ )
        for ( j = 0 ; j < c ; j++ )
        {
            if ( cTemp[i][j] == '*' )
            {
                LeftMem[i][j] = LNum ;
                for ( k = j + 1 ; k < c ; k++ )
                {
                    //每一列连续的 * 记为同一个值
                    if ( cTemp[i][k] == '*' ) 
                    {
                        LeftMem[i][k] = LNum ;
                    }
                    else {
                        j = k - 1 ;
                        break ;
                    }
                }
                if ( k >= c )
                {
                    k = 0 ;
                    j = c ;
                }

                LNum++ ;
            }
        }
    for ( i = 0 ; i < c ; i++ )
    {
        for ( j = 0 ; j < r ; j++ )
        {
            if ( cTemp[j][i] == '*' )
            {
                //行跟列有'*'交叉，则匹配
                map[LeftMem[j][i]][RNum] = true ;

                for ( k = j + 1 ; k < r ; k++ )
                {
                    if ( cTemp[k][i] != '*' )
                    {
                        j = k - 1 ;
                        break ;
                    }
                    else {
                        map[LeftMem[k][i]][RNum] = true ;
                    }
                }
                if ( k >= r )
                {
                    k = 0 ;
                    j = r ;
                }

                RNum++ ;
            }
        }
    }
}

bool FindPath( int u )
{
    int v ;
    
    for ( v = 0 ; v < RNum ; v++ )
    {
        if ( !use[v] && map[u][v] )
        {
            use[v] = true ;
            if ( link[v] == -1 || FindPath( link[v] ) )
            {
                link[v] = u ;
                return true ;
            }
        }
    }
    return false ;
}

void Init( void )
{
    int R , C ;
    int i ;

    scanf("%d %d", &R, &C) ;

    for ( i = 0 ; i < R ; i++ )
    {
        scanf("%s", &cTemp[i]) ;
    }

    Build( R, C ) ;
    
    int ans = 0 ;

    for ( i = 0 ; i < LNum ; i++ )
    {
        memset( use, 0, sizeof(use) );

        if ( FindPath(i) )
            ans++ ;
    }

    printf("%d\n", ans) ;
}

int main()
{
    Init() ;

    return 0 ;
}
posted on 2008-10-31 21:29 巫 阅读(412) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理