• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
            二分圖匹配，關鍵：建圖
            

            #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 巫 閱讀(422) 評論(0)  編輯 收藏 引用  所屬分類: 圖論 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



欧美亚洲日本久久精品|
久久久久一本毛久久久|
精品少妇人妻av无码久久|
国产精品美女久久久久|
一本大道久久a久久精品综合|
色婷婷久久综合中文久久一本|
久久无码高潮喷水|
久久精品免费观看|
精品国产乱码久久久久软件|
91精品无码久久久久久五月天
|
久久精品国产精品青草|
成人亚洲欧美久久久久|
亚洲精品乱码久久久久66|
99久久人人爽亚洲精品美女|
性欧美大战久久久久久久久|
精品一久久香蕉国产线看播放|
日日噜噜夜夜狠狠久久丁香五月|
69SEX久久精品国产麻豆|
精品久久久久成人码免费动漫
|
久久国产精品无|
国产精品久久久久jk制服|
久久婷婷五月综合国产尤物app|
国产成人精品久久综合|
国产成年无码久久久久毛片|
久久久亚洲AV波多野结衣|
久久一区二区三区免费|
99久久精品这里只有精品|
久久久久久狠狠丁香|
国产精品岛国久久久久|
三上悠亚久久精品|
久久精品麻豆日日躁夜夜躁|
久久精品国产久精国产果冻传媒
|
精品久久久久香蕉网|
午夜精品久久久久久毛片|
狠狠综合久久综合88亚洲|
久久综合亚洲鲁鲁五月天|
久久天天躁夜夜躁狠狠|
无码国内精品久久人妻|
久久精品中文字幕无码绿巨人|
久久免费的精品国产V∧
|
久久这里只有精品视频99|